Submission #81715

#	Time	Username	Problem	Language	Result	Execution time	Memory
81715		ffrich	Zamjena (COCI18_zamjena)	C++14	70 / 70	486 ms	19976 KiB

zamjena

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14