제출 #81693

#제출 시각아이디문제언어결과실행 시간메모리
81693aminraZamjena (COCI18_zamjena)C++14
70 / 70
150 ms23320 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int MAXN = (int)1e5 + 7; const int infint = (int)1e9; const ll inf = (ll)1e18; string s1[MAXN], s2[MAXN]; string val[MAXN]; vector<int> G[MAXN], comp[MAXN]; int visited[MAXN], cmp = 0, n; void dfs(int u) { comp[cmp].push_back(u); visited[u] = 1; for (auto v : G[u]) if(!visited[v]) dfs(v); } unordered_map<string, int> M; ll get(string s) { if(s[0] < '0' || s[0] > '9') return 0; else return 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; i++) cin >> s1[i]; for (int i = 0; i < n; i++) cin >> s2[i]; set<string> S; for (int i = 0; i < n; i++) if(get(s1[i]) == 0) S.insert(s1[i]); for (int i = 0; i < n; i++) if(get(s2[i]) == 0) S.insert(s2[i]); int cnt = 0; for (auto u : S) M[u] = cnt++; for (int i = 0; i < n; i++) { if(get(s1[i]) == 1) { if(get(s2[i]) == 1) { if(s1[i] != s2[i]) return cout << "NE", 0; } else { if(val[M[s2[i]]] != "" && val[M[s2[i]]] != s1[i]) return cout << "NE", 0; val[M[s2[i]]] = s1[i]; } } else { if(get(s2[i]) == 1) { if(val[M[s1[i]]] != "" && val[M[s1[i]]] != s2[i]) return cout << "NE", 0; val[M[s1[i]]] = s2[i]; } else { G[M[s1[i]]].push_back(M[s2[i]]); G[M[s2[i]]].push_back(M[s1[i]]); } } } for (int i = 0; i < cnt; i++) if(!visited[i]) dfs(i), cmp++; for (int i = 0; i < cmp; i++) { string fir; for (auto u : comp[i]) if(val[u] != "") fir = val[u]; if(fir == "") continue; for (auto u : comp[i]) if(val[u] != "" && val[u] != fir) return cout << "NE", 0; } cout << "DA"; }
#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...