oj.uz

Submission #81715

# Submission time Handle Problem Language Result Execution time Memory
81715 2018-10-26T10:01:09 Z ffrich Zamjena (COCI18_zamjena) C++14
70 / 70
 486 ms 19976 KB 
#include<cstdio>
#include<iostream>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>

using namespace std;

	string niz1[50002],niz2[50002];

	map < string , vector < string > > Equal;
	map < string , string > M;
	
	set < string > USED;

	bool pocetak(string a){
		
		if(a[0] <= '9' && a[0] >= '0') return true;
		return false;
		
	}

	// niz2 od 0 
	// niz1 od n

int main(){
	int n; cin >> n;
	for(int i = 0; i < n; i++) cin >> niz1[i];
	for(int j = 0; j < n; j++){	
		cin >> niz2[j];
		if(pocetak(niz1[j]) && pocetak(niz2[j])){
			if(niz1[j] != niz2[j]){
				cout << "NE" << endl;
				return 0;
			}
		}
		else if(pocetak(niz1[j])){
			if(M.count(niz2[j]) == 0) M[niz2[j]] = niz1[j];
			else{
				if(M[niz2[j]] == niz1[j]) continue;
				else{
					cout << "NE" << endl;
					return 0;
				}
			}
		}
		else if(pocetak(niz2[j])){
			if(M.count(niz1[j]) == 0) M[niz1[j]] = niz2[j];
			else{
				if(M[niz1[j]] == niz2[j]) continue;
				else{
					cout << "NE" << endl;
					return 0;
				}
			}
		}
		else{
			Equal[niz2[j]].push_back(niz1[j]);
			Equal[niz1[j]].push_back(niz2[j]);
		}
	}
	
	queue < string > Q;
	map<string,string>::iterator it = M.begin();
	for(;it != M.end(); it++){
		Q.push(it->first);
		USED.insert(it->first);
	} 

	while(!Q.empty()){
		
		string curr = Q.front(); Q.pop();
		string post = M[curr];
		
		for(int i = 0; i < Equal[curr].size(); i++){
			
			if(M.count(Equal[curr][i]) == 0) M[Equal[curr][i]] = post;
			else{
				if(M[Equal[curr][i]] != post){
					cout << "NE" << endl;
					return 0;
				}
			}
			
			if(USED.find(Equal[curr][i]) == USED.end()){
				USED.insert(Equal[curr][i]);
				Q.push(Equal[curr][i]);
			}
	
		}
		
	}
	

	cout << "DA" << endl;
	return 0;
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < Equal[curr].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 4 ms 3448 KB Output is correct
3 Correct 4 ms 3524 KB Output is correct
4 Correct 6 ms 3536 KB Output is correct
5 Correct 4 ms 3536 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3664 KB Output is correct
2 Correct 4 ms 3712 KB Output is correct
3 Correct 4 ms 3712 KB Output is correct
4 Correct 5 ms 3712 KB Output is correct
5 Correct 5 ms 3712 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3712 KB Output is correct
2 Correct 5 ms 3712 KB Output is correct
3 Correct 4 ms 3712 KB Output is correct
4 Correct 5 ms 3712 KB Output is correct
5 Correct 5 ms 3712 KB Output is correct
6 Correct 5 ms 3712 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3964 KB Output is correct
2 Correct 8 ms 3964 KB Output is correct
3 Correct 14 ms 4348 KB Output is correct
4 Correct 11 ms 4348 KB Output is correct
5 Correct 18 ms 4476 KB Output is correct
6 Correct 12 ms 4476 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5236 KB Output is correct
2 Correct 120 ms 8872 KB Output is correct
3 Correct 75 ms 9212 KB Output is correct
4 Correct 127 ms 12076 KB Output is correct
5 Correct 486 ms 19976 KB Output is correct
6 Correct 308 ms 19976 KB Output is correct