Submission #124496

#TimeUsernameProblemLanguageResultExecution timeMemory
124496andreiomdZamjena (COCI18_zamjena)C++11
42 / 70
1077 ms3372 KiB
#include <iostream> #include <cstring> #include <map> using namespace std; const int NMAX = 5e4 + 5, MMAX = 15; int N, M, n; char S[MMAX]; bool OK = true; struct Element { int X; char Y[MMAX]; }; Element A[NMAX], B[NMAX]; map < string, int > mp; map < string, bool > Sel; inline void Read () { ios_base :: sync_with_stdio(false); cin.tie(NULL); cin >> N; for(int i = 1; i <= N; ++i) { cin >> (S + 1); M = strlen(S + 1); bool Nr = true; for(int j = 1; j <= M && Nr; ++j) if(!isdigit(S[j])) Nr = false; if(Nr) { n = 0; for(int j = 1; j <= M; ++j) n = n * 10 + (S[j] - '0'); A[i].X = n; } else for(int j = 1; j <= M; ++j) A[i].Y[j] = S[j]; } for(int i = 1; i <= N; ++i) { cin >> (S + 1); M = strlen(S + 1); bool Nr = true; for(int j = 1; j <= M && Nr; ++j) if(!isdigit(S[j])) Nr = false; if(Nr) { n = 0; for(int j = 1; j <= M; ++j) n = n * 10 + (S[j] - '0'); B[i].X = n; } else for(int j = 1; j <= M; ++j) B[i].Y[j] = S[j]; } return; } inline void Solve () { for(int i = 1; i <= N; ++i) if(A[i].X && B[i].X) if(A[i].X != B[i].X) { OK = false; break; } if(!OK) return; bool done = true; int op = 0; while(done && op * N <= 5000000) { ++op; done = false; for(int i = 1; i <= N; ++i) if(A[i].X && B[i].X) continue; else { if(A[i].X) { string V; M = strlen(B[i].Y + 1); for(int j = 1; j <= M; ++j) V.push_back(B[i].Y[j]); if(Sel[V]) { if(mp[V] != A[i].X) { OK = false; return; } else continue; } else { Sel[V] = true; mp[V] = A[i].X; } } else { if(B[i].X) { string V; M = strlen(A[i].Y + 1); for(int j = 1; j <= M; ++j) V.push_back(A[i].Y[j]); if(Sel[V]) { if(mp[V] != B[i].X) { OK = false; return; } else continue; } else { Sel[V] = true; mp[V] = B[i].X; } } else { if(strcmp(A[i].Y + 1, B[i].Y + 1) == 0) continue; string V1, V2; int m1 = (int)strlen(A[i].Y + 1); int m2 = (int)strlen(B[i].Y + 1); for(int j = 1; j <= m1; ++j) V1.push_back(A[i].Y[j]); for(int j = 1; j <= m2; ++j) V2.push_back(B[i].Y[j]); if(Sel[V1] && Sel[V2]) { if(mp[V1] != mp[V2]) { OK = false; return; } else continue; } else { if(Sel[V1]) { Sel[V2] = true; mp[V2] = mp[V1]; } else { if(Sel[V2]) { Sel[V1] = true; mp[V1] = mp[V2]; } else done = true; } } } } } } return; } int main() { Read(); Solve(); if(OK) cout << "DA"; else cout << "NE"; cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...