OJ Board

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main
{
	static Map<String, Author> authorIdx;
    
	public static void main(String[] args) throws IOException {

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintStream cout = System.out;
    	StringBuffer sbOut = new StringBuffer();

        String line = reader.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        int numScenarios = Integer.parseInt( tokenizer.nextToken());		
        
        for (int i = 0; i < numScenarios; i++)
        {
        	authorIdx = new HashMap<String, Author>();
        	
        	// Database Size and Name Size
            line = reader.readLine();
            while (line.trim().length() == 0)
            {
            	line = reader.readLine();
            }
            tokenizer = new StringTokenizer(line);
            int numPapers = Integer.parseInt( tokenizer.nextToken());		
            int numNames = Integer.parseInt( tokenizer.nextToken());		

            String[] papers = new String[numPapers];
            String[] names = new String[numNames];
            
            // read database
            for (int j = 0; j < numPapers; j++) 
            {
            	line = reader.readLine();
            	papers[j] = line;
            }
            
            // read names
            for (int j = 0; j < numNames; j++) 
            {
                line = reader.readLine();
                names[j] = line;
                names[j] = trim(line);
                createAuthor(names[j]);
            }
            
            // Solve it
            // 1. Build Author Graph
            for (String paper : papers)
            {
            	Collection<String> paperAuthors = splitPaper( paper);
            	for (String authorName : paperAuthors)
            	{
            		Author author = authorIdx.get( authorName);
        			if (author == null)
        			{
        				author = createAuthor(authorName);
        			} else 
        			{
        				for (String coAuthorName : paperAuthors)
        				{
        					if (!coAuthorName.equals( authorName))
        					{
        						Author coAuthor = authorIdx.get( coAuthorName);
        						if (coAuthor == null)
        						{
        	        				coAuthor = createAuthor( coAuthorName);
        						}	
       							author.addCoAuthor( coAuthor);
        					}	
                		}
                	}
            	}
            }
            
            // 2. Measure distance from Erdos
            Author erdosHimself = authorIdx.get( "Erdos, P.");
            if (erdosHimself == null)
            {
            	erdosHimself = createAuthor( "Erdos, P.");
            }
            erdosHimself.erdosNo = 0;
            
            List<Author> hasToBeProcessed = new ArrayList<Author>();
            hasToBeProcessed.add( erdosHimself);
            while(!hasToBeProcessed.isEmpty())
            {
            	Author author = hasToBeProcessed.remove( 0); 
        		author.processed = true;
        		for (Author a : author.getCoAuthors())
        		{
        			if ((author.erdosNo + 1) < a.erdosNo)
        			{	
        				a.erdosNo = author.erdosNo + 1;
        			}	
        			if (!a.processed && !hasToBeProcessed.contains( a))
        			{
        				hasToBeProcessed.add(a);
        			}
        		}
            }
            
            // Dump Result
            sbOut.append( "Scenario " + (i+1) + "\n");
            for (String name : names) 
            {
            	Author author = authorIdx.get( name);
            	if (author != null)
            	{
            		String erdNr;
            		if (author.erdosNo == Integer.MAX_VALUE)
            		{
            			erdNr = "infinity";
            		} else {
            			erdNr = String.valueOf( author.erdosNo);
            		}
            		sbOut.append(name + " " + erdNr + "\n");
            	}
            }
        }
        
        cout.print(sbOut.toString());
	}

	static Collection<String> splitPaper(String paper)
	{
		// 0: name vollständig gelesen, erwarte neuen namen
		// 1: Nachname gelesen, erwarte vorname
		
		paper = trim(paper);
		
		int colon = paper.indexOf( ':');
		if (colon > 0)
		{
			paper = paper.substring( 0, colon);
		}	
		
		int state = 0;
		int lastIndex = 0;
		
		Collection<String> names = new HashSet<String>();
		
		int nameStart = 0;
		while (true)
		{
			int comma = paper.indexOf( ',', lastIndex);
			if (comma != -1)
			{
				if (state == 0)
				{
					nameStart = lastIndex;
					state = 1;
				} else 
				{
					String name = paper.substring( nameStart, comma);
					name = name.trim();
					
					names.add( name);
					state = 0;
				}
				lastIndex = comma+1;
			} else {
				
				if (state == 1)
				{
					String name = paper.substring( nameStart);
					name = name.trim();
					names.add( name);
				}				
				break;
			}
		}		
		return names;
	}
	
	static Author createAuthor(String name)
	{
		Author a = new Author(name);
		authorIdx.put( name, a);
		return a;
	}
	
    static String trim(String s)
    {
		int from = 0;
		int to = s.length()-1;
		
		while (s.charAt( from) == ' ' || s.charAt( from) == '\t')
		{
			from++;
		}
		while (Character.isWhitespace( s.charAt( to)))
		{
			to--;
		}
    	
		StringBuffer sb = new StringBuffer();
		for (int i=from; i<=to; i++)
		{
			char c = s.charAt( i); 
			if (c == ' ')
			{
				sb.append( c);
				while(i<=to && s.charAt( i+1) == ' ')
				{
					i++;
				}
			} else
			{
				sb.append( c);
			}
		}
		return sb.toString();
    }
    	
	static class Author
	{
		String name;
		int erdosNo;
		boolean processed;
		Collection<Author> coAuthorOf;
		
		Author(String name)
		{
			this.erdosNo = Integer.MAX_VALUE;
			this.processed = false;
			this.name = name;
			coAuthorOf = new HashSet<Author>();
		}
		
		Collection<Author> getCoAuthors()
		{
			return coAuthorOf;
		}
		
		void addCoAuthor(Author a)
		{
			coAuthorOf.add( a);
		}

		@Override
		public String toString()
		{
			return name;
		}

		@Override
		public boolean equals(Object obj)
		{
			return name.equals( ((Author)obj).name);
		}

		@Override
		public int hashCode()
		{
			return name.hashCode();
		}		
	}	
}

Code: Select all

5
1 2
Erdos, P. , ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P., ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P.,  ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P.,  ghj,P.:fh
ghj,P.
ghj, P.

Code: Select all

Scenario 1
ghj,P. infinity
ghj, P. infinity
Scenario 2
ghj,P. infinity
ghj, P. 1
Scenario 3
ghj,P. infinity
ghj, P. 1
Scenario 4
ghj,P. 1
ghj, P. infinity

Code: Select all

Scenario  1
ghj,P. infinity
ghj, P. infinity
Scenario  2
ghj,P. infinity
ghj, P. 1
Scenario  3
ghj,P. infinity
ghj, P. 1
Scenario  4
ghj,P. 1
ghj, P. infinity
Scenario  5
ghj, P. infinity
ghj, P. infinity

Code: Select all

#include <iostream>
#include <map>
#include <cstring>
#include <string>
#include <queue>
#include <cctype>

using namespace std;

int p, n;
map<string,int> aut;
int mat [ 1000 ][ 1000 ];
int nameCnt;
int len [ 1000 ];
int color [ 1000 ];

void preprocess();
void process( string name );

int main()
{
	int tNo;
	char tLine [ 1000 ];
	string lineStr;
	string pStr [ 1000 ];
	int pCnt;

	cin >> tNo;
	for ( int i = 0; i < tNo; i++ )
	{
		nameCnt = 0;
		aut.clear();
		memset( mat, 0, sizeof(mat) );
		cin >> p >> n;
		cin.ignore();
		for ( int j = 0; j < p; j++ )
		{
			cin.getline( tLine, 1000, '\n' );
			lineStr = tLine;
			int comInd [ 1000 ];
			//
			int comCnt = 0;
			comInd[ comCnt++ ] = -2;
			for ( int k = 0; k < lineStr.length(); k++ )
			{
				if ( lineStr[ k ] == ',' || lineStr[ k ] == ':' )
				{
					comInd[ comCnt++ ] = k;
				}
			}
			
			pCnt = 0;
			for ( int k = 2; k < comCnt; k += 2 )
			{
				int stInd, endInd;
				stInd = comInd[ k - 2 ] + 2;
				endInd = comInd[ k ] - 1;
				pStr[ pCnt++ ] = lineStr.substr( stInd, endInd - stInd + 1 );
				if ( aut.find( lineStr.substr( stInd, endInd - stInd + 1 ) ) == aut.end() )
				{
					aut[ lineStr.substr( stInd, endInd - stInd + 1 ) ] = nameCnt++;
				}
			}
			//

			for ( int i = 0; i < pCnt; i++ )
			{
				for ( int j = i + 1; j < pCnt; j++ )
				{
					mat[ aut[ pStr[ i ] ] ][ aut[ pStr[ j ] ] ] = mat[ aut[ pStr[ j ] ] ][ aut[ pStr[ i ] ] ] = 1;
			   }
			}
		}
	
		preprocess();
		cout << "Scenario " << i + 1 << endl;
		for ( int k = 0; k < n; k++ )
		{
			cin.getline( tLine, 1000, '\n' );
			lineStr = tLine;
			process( lineStr );
		}
	}

	return 0;
}

void process( string name )
{
	cout << name << " ";
	if ( aut.find( name ) == aut.end() )
	{
		cout << "infinity" << endl;
	}
	else
	{
		if ( len[ aut[ name ] ] == -1 )
		{
			cout << "infinity" << endl;
		}
		else
		{
			cout << len[ aut[ name ] ] << endl;
		}
	}
}

void preprocess()
{
	for ( int i = 0; i < nameCnt; i++ )
	{
		len[ i ] = -1;
	}

	if ( aut.find("Erdos, P.") != aut.end() )
	{
		// bfs
		queue<int> q;
		memset( color, 0, sizeof(color) );

		q.push( aut[ "Erdos, P." ] );
		color[ aut[ "Erdos, P." ] ] = 1;
		len[ aut[ "Erdos, P." ] ] = 0;

		while ( !q.empty() )
		{
			int u = q.front();
			q.pop();

			for ( int i = 0; i < nameCnt; i++ )
			{
				if ( mat[ u ][ i ] == 1 && color[ i ] == 0 )
				{
					q.push( i );
					color[ i ] = 1;
					len[ i ] = len[ u ] + 1;
				}
			}
		}
	}
}

Code: Select all

#include <iostream>
#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <string>

using namespace std;

struct adj {
	vector < map<string, adj>::iterator > neip;
	int dis;
	
	adj() : dis(-1) {
		neip.reserve(40);
	}
	
};


int main(){
	int tc, p, n, cas=0;
	cin>>tc;
	while(++cas<=tc){
		cin>>p>>n;
		map<string, adj> m;
		
		
		for (int i=0; i<p; ++i){
			vector <map<string, adj>::iterator> tn; tn.reserve(80); string ts; ts.reserve (15);
			char c;
			while (true){
				while (!isalpha((c=getchar())));
				bool firstcom=false;
				do{
					if (c==',') firstcom=true;
					ts.push_back(c);
					c=getchar();
					
				} while (c!=':' && (!firstcom||c!=','));

				m[ts];
				tn.push_back(m.find(ts));
				ts.clear();
				if(c==':') break;
			}
			int neinum=tn.size();
			for (int i=0; i<neinum; ++i){
				for (int j=0; j<neinum; ++j){ if (i==j) continue;
					tn[j]->second.neip.push_back(tn[i]);
				}
			}
			while (getchar()!='\n');
		}
		
		vector<string> names(n); 
		for (int i=0; i<n; ++i){
			while (isspace(cin.peek())) getchar();
			getline(cin, names[i]);
		}
		
	
		int lev;
		queue <map<string, adj>::iterator> bfs;
		bfs.push(m.find("Erdos, P."));
		bfs.front()->second.dis=0; // his own Erdos num
		while (!bfs.empty()){
			map<string, adj>::iterator fro=bfs.front();
			lev=fro->second.dis+1;
			int neisize=fro->second.neip.size();
			for (int i=0; i<neisize; ++i){
				if (fro->second.neip[i]->second.dis==-1){
					fro->second.neip[i]->second.dis=lev;
					bfs.push(fro->second.neip[i]);
				}
			}
			bfs.pop();
		}
		
		printf("Scenario %d\n",cas);
		for (int i=0; i<n; ++i){
			cout<<names[i];
			map<string, adj>::iterator it=m.find(names[i]);
			if (it==m.end()|| it->second.dis==-1){
				printf(" infinity\n");
			}
			else{
				printf(" %d\n",it->second.dis);
			}
		}
	}
	
	return 0;
}