OJ Board

Code: Select all

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <map>
using namespace std;

//
map <string , int> val;
#define infinty 999999
#define max_names_per_line 101
//

// returns the minimum "erdos number" in a paper
int minimum(string **names , int i)
{
	int min = val[names[i][0]];
	for(int j = 1; j<max_names_per_line && names[i][j] != ""; j++)
	{
		min = (min > val[names[i][j]])? val[names[i][j]] : min;
	}
	return min;
}
// if you want to view the names with their "erdos numbers"
void view(string **names , int p)
{
	cout<<"..........................................................\n";
	for(int i = 0; i<p; i++)
	{
		for(int j=0;j<max_names_per_line && names[i][j] != ""; j++)
		{
			cout<<names[i][j]<<":"<<val[names[i][j]]<<"   ";
		}
		cout<<endl;
	}
	cout<<"..........................................................\n";
}
// checks if we are done meaning that there is no more operations to do
// and every name is with his correct "erdos number"
bool finished(string **names, int p)
{
	for(int i = 0; i<p; i++)
	{
		int x = minimum(names,i);
		for(int j = 0; j<max_names_per_line && names[i][j] != ""; j++)
		{
			if(val[names[i][j]] != x && val[names[i][j]] != x+1)
				return 0;
		}
	}
	return 1;
}
//

int main()
{
	int T;
	string line;
	int Scenario = 1;
	cin>>T;

	while(T--)
	{
		int p,n;
		cin>>p>>n;
		string **names = new string *[p];

		// reding the papers and implinting the names in 2D array
		for(int i = 0; i<p; i++)
		{
			bool b = 0;
			names[i] = new string [max_names_per_line];
			int na = 0;
			char ch;

			while(cin >> ch && ch != ':')
			{
				if(ch == ',')
				{
					if(b == 0)
					{
						b = 1;
						names[i][na] += ", ";
					}
					else
					{
						val[names[i][na]] = infinty;
						na++;
						b = 0;
					}
				}
				else
					names[i][na]+=ch;
			}

			val[names[i][na]] = infinty;
			getline(cin,line);
		}

		val[""] = infinty;
		val["Erdos, P."] = 0;
		
		// scanning the array and giving erdos number to each name in O(n^2) i think, but didn't pass the time limit
		/*
		int pp = p;
		while(pp--)
		{
			for(int i = 0; i<p; i++)
			{
				int min = minimum(names , i);
				for(int k=0;k<max_names_per_line && names[i][k] != "";k++)
				{
					if(val[names[i][k]] > min)
						val[names[i][k]] = min+1;
				}
			}
		}
		*/
		
		// scanning the array and giving erdos number to each name in O(n) i think, and passed within 2.185
		while(1)
		{
			for(int i = 0; i<p; i++)
			{
				int min = minimum(names , i);
				for(int k=0;k<max_names_per_line && names[i][k] != "";k++)
				{
					if(val[names[i][k]] > min)
						val[names[i][k]] = min+1;
				}
			}
			if(finished(names,p))
				break;
		}

		// printing the results
		cout<<"Scenario "<<Scenario++<<endl;
		for(int i = 0; i<n; i++)
		{
			getline(cin,line);
			cout<<line<<' ';
			if(val[line] == infinty)
				cout<<"infinity";
			// expecting the judge to view the "erdos number" for a name that isn't mentioned in the papers
			// and the judge does
			else if(val[line] == 0 && line != "Erdos, P.")
				cout<<"infinity";
			else
				cout<<val[line];
			cout<<endl;
		}
	}
	return 0;
}

Code: Select all

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

Code: Select all

Scenario 1
ghj,P. infinity
ghj, P. infinity

Code: Select all

Scenario 1
ghj,P. 1
ghj, P. 1

Code: Select all

2
4 4
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First oder derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.
Reisig, W.

1 2
Smith, M.N. , Erdos, P.: Newtonian forms of prime factor matrices
Smith, M.N.
Smith, M.N.

Code: Select all

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Reisig, W. 1
Scenario 2
Smith, M.N. 1
Smith, M.N. 1

Code: Select all

1
3 5
Smith, T.H., Martin, G., Erdos, P.: Newtonian forms of prime factors
a, e., b, f., c, g., d, h., Smith, T.H.: Something
Smith, T.H., Chen, X.: First order derivates in structured programming
Smith, T.H.
a, e.
a, f.
Chen, X.
Chen, X

Code: Select all

Scenario 1
Smith, T.H. 1
a, e. 2
a, f. infinity
Chen, X. 2
Chen, X infinity

Code: Select all

1
12 15
Erdos, P., C, C: asdf
Erdos, P., B, B: asdf
Erdos, P., A, A: asdfa
B, B, G, G: asdf
A, A, H, H: asdf
H, H, I, I: asdf
I, I, J, J, K, K: asdf
J, J, L, L: asdf
L, L, F, F: asdf
C, C, F, F: aadsf
F, F, D, D, E, E: asdf
M, M, N, N, O, O: asdf
A, A
B, B
C, C
D, D
E, E
F, F
G, G
H, H
I, I
J, J
K, K
L, L
M, M
N, N
O, O

Code: Select all

Scenario 1
A, A 1
B, B 1
C, C 1
D, D 3
E, E 3
F, F 2
G, G 2
H, H 2
I, I 3
J, J 4
K, K 4
L, L 3
M, M infinity
N, N infinity
O, O infinity

Code: Select all

 2
  4    3
    Smith,   M.N.,  Martin,    G.,    Erdos, P.: Newtonian forms of prime factor matrices 
Erdos,              P.,  Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First oder derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.
12 18
Erdos, P., C, C., FUFAIL, F: asdf
Erdos, P., B, B.: asdf
Erdos, P., A, A.: asdfa
B, B., G, G.: asdf
A, A., H, H.: asdf
H, H., I, I.: asdf
I, I., J, J., K, K.: asdf
J, J., L, L.: asdf
L, L., F, F.: asdf
C, C., F, F.: aadsf
F, F., D, D., E, E.: asdf
M, M., N, N., O, O.: asdf
A, A.
B, B.
C, C.
D, D.
E, E.
F, F.
G, G.
H, H.
I, I.
J, J.
K, K.
L, L.
M, M.
N, N.
O, O.
WTF, F.
WTF., F
WTF, U.

Code: Select all

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Scenario 2
A, A. 1
B, B. 1
C, C. 1
D, D. 3
E, E. 3
F, F. 2
G, G. 2
H, H. 2
I, I. 3
J, J. 4
K, K. 4
L, L. 3
M, M. infinity
N, N. infinity
O, O. infinity
WTF, F. infinity
WTF., F infinity
WTF, U. infinity

Code: Select all

4
1 1
Erdos, P. , ghj, P.:fh
ghj, P.
1 1
Erdos, P., ghj, P.:fh
ghj, P.
1 1
Erdos, P.,  ghj, P.:fh
ghj, P.
1 1
Erdos, P.,  ghj,P.:fh
ghj, P.

Code: Select all

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

Code: Select all

//___A,___B -> A,_B

#include <algorithm>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef map<string, int> index;
typedef map<int, set<int>> graph;

const int infinity = 1000000;

string transformInValid(string name){
    string newName = "";

    for (int l = 0; l < name.length(); l++){
        if (name[l] != ' '){
            newName += name[l];

            if (name[l] == ',')
                newName += ' ';
        }
    }

    //cout << "$$" << name << ">>>" << newName << "<<<\n";
    return newName;
}

void newAuthors(index &ind, graph &g, string paper, int &newId){

    bool isStage3 = false;
    string name;
    vector<int> newAuthors;

    //Possiveis formas do nome do autor:

    for (char s : paper){
        if (s == ' ') continue;

        if (s == ':'){
            if (isStage3){
                auto p = ind.insert(make_pair(name, newId));
                g.insert(make_pair(newId, set<int>()));

                //if the author already exists, there is no need to create a new id
                if (p.second)
                    newId++;

                newAuthors.push_back(p.first->second);
            }
        }
        else{
            if (s == ','){
                if (isStage3){
                    auto p = ind.insert(make_pair(name, newId));
                    g.insert(make_pair(newId, set<int>()));

                    //if the author already exists, there is no need to create a new id
                    if (p.second)
                        newId++;

                    newAuthors.push_back(p.first->second);

                    isStage3 = false;
                    name.clear();
                }
                else{
                    isStage3 = true;
                    name += ", ";
                }
            }
            else
                name += s;
        }
    }

    //update the adjacent list
    for (int author : newAuthors){
        for (int coAuthor = 0; coAuthor < newAuthors.size(); coAuthor++){
            if (newAuthors[coAuthor] == author) continue;

            g[author].insert(newAuthors[coAuthor]);
            //cout << "Inserting ID " << newAuthors[coAuthor] << "in " << author << endl;
        }
    }

}

int main(){
    int cases, p, n;

    cin >> cases;
    cin.ignore();

    for (int scenario = 0; scenario < cases; scenario++){
        int id = 1;         //erdos has the id = 0
        bool first = true;
        bool entrou = false;

        string paper;
        index table;
        graph g;

        //Erdos is the first element in the graph
        g.insert(make_pair(0, set<int>()));
        table.insert(make_pair("Erdos, P.", 0));

        cin >> p >> n;
        cin.ignore();

        for (int i=0; i<p; i++){
            getline(cin, paper);
            newAuthors(table, g, paper, id);
        }

        /*
        cout << "Current graph:\n";
        for (auto itGraph = g.begin(); itGraph != g.end(); itGraph++){
            cout << itGraph->first << ":\n";
            for (auto itSet = itGraph->second.begin(); itSet != itGraph->second.end(); itSet++)
                cout << *itSet << " ";
            cout << endl;
        }*/

        vector<int> distances(table.size());
        iota(distances.begin(), distances.end(), infinity);
        distances[0] = 0;

        for (int i=0; i<g.size(); i++){
            for (int otherAuthor : g[i]){
                if (distances[otherAuthor] > distances[i] + 1)
                    distances[otherAuthor] = distances[i] + 1;
            }
        }


        //read the authors whom the erdos number must be found
        cout << "Scenario " << scenario+1 << endl;
        for (int i = 0; i < n; i++){
            getline(cin, paper);

            string name = transformInValid(paper);

            string searchName = name;
            //searchName.erase(remove(searchName.begin(),searchName.end(),' '),searchName.end());

            if (!first)
                cout << endl;
            else
                first = false;

            auto result = table.find(searchName);
            if (result == table.end())
                cout << name << " infinity";
            else{
                int erdosNumber = distances[result->second];
                if (erdosNumber < infinity)
                    cout << name << " " << erdosNumber;
                else
                    cout << name << " infinity";
            }

            entrou = true;
        }

        if (entrou && scenario < cases-1)
            cout << endl;
    }

    return 0;
}

Code: Select all

#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<vector>
#include<queue>
#define sz 10005
#define inf 999999
using namespace std;

int main()
{
    string str, S;
	bool flag, vs[sz];
    long f, id, ind, ln, P, N, T, erdos[sz];
    
    scanf("%d", &T);
    
    for(long i=1;i<=T;i++)
    {
        scanf("%d %d", &P, &N);
        getchar();
        
        id = 1;
        map<string, long>myMap;
        vector<long>v, myVec[sz];
        
        for(long j=1;j<=P;j++)
        {
            getline(cin, str);

			S = "";
			ln = str.length();
			for(int k=0, cnt=0;k<ln;k++)
			{
				if(str[k] == ',')
					cnt++;

				if(cnt == 2 || str[k]==':')
				{
					while(S[0] == ',' || S[0]==' '){
						S.erase(0, 1);
					}

					if(myMap[S] == 0)
						myMap[S] = id++;

					v.push_back(myMap[S]);

					//cout<<S<<endl;

					S="";
					cnt=0;

					if(str[k] == ':')
						break;
				}
				if(str[k] != ' ')
					S.push_back(str[k]);
			}
            
            ln = v.size();
            
            for(long k=0;k<ln;k++)
            {
                for(long l=0;l<ln;l++)
                {
                    if(k != l)
                        myVec[v[k]].push_back(v[l]);
                }
            }

			v.clear();
        }

		/*for(long j=1;j<=id;j++)
		{
			cout<<j<<"--->";
			for(long k=0;k<myVec[j].size();k++)
				cout<<myVec[j][k]<<" ";
			cout<<endl;
		}*/

		for(long j=1;j<=id;j++)
		{
			erdos[j] = inf;
			vs[j] = false;
		}

		queue<long>Q;
		
		Q.push(myMap["Erdos,P."]);
		erdos[myMap["Erdos,P."]] = 0;
		vs[myMap["Erdos,P."]] = true;

		while(!Q.empty())
		{
			f = Q.front();

			ln = myVec[f].size();
			for(long j=0;j<ln;j++)
			{
				ind = myVec[f][j];
				if(!vs[ind])
				{
					Q.push(ind);
					erdos[ind] = erdos[f] + 1;
					vs[ind] = true;
				}
			}
			Q.pop();
		}

		/*for(long j=1;j<=id;j++)
			cout<<erdos[j]<< " ";
		cout<<endl;*/

		cout<<"Scenario "<<i<<endl;
		for(long j=1;j<=N;j++)
		{
			getline(cin, str);

			cout<<str<<" ";

			S = "";
			ln = str.length();
			for(int k=0;k<ln;k++)
			{
				if(str[k] != ' ')
					S.push_back(str[k]);
			}

			//cout<<S<<endl;

			if(erdos[myMap[S]] == inf)
				cout<<"infinity"<<endl;

			else
				cout<<erdos[myMap[S]]<<endl;
		}
    }
    return 0;
}