Submission #237097

#TimeUsernameProblemLanguageResultExecution timeMemory
237097DanShadersZamjena (COCI18_zamjena)C++17
14 / 70
36 ms7544 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define all(x) begin(x), end(x) #define x first #define y second typedef long long ll; typedef long double ld; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<T>>; const int MAX_N = 5e4 + 10; string a[MAX_N], b[MAX_N]; map<string, int> varId; vector<int> edges[MAX_N]; vector<int> owned[MAX_N]; char used[MAX_N]; int m = 0; int getVarId(string s) { if (!varId.count(s)) varId[s] = m++; return varId[s]; } int dfs(int u) { if (used[u]) return -2; used[u] = 1; int pop = -2; for (int v : edges[u]) { int n = dfs(v); if (pop == -2) pop = n; if (pop != n) return -1; } for (int v : owned[u]) { if (pop == -2) pop = v; if (pop != v) return -1; } return pop; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> b[i]; for (int i = 0; i < n; ++i) { bool av = 0, bv = 0; int d1 = -1, d2 = -1; if (isdigit(a[i][0])) { d1 = stoi(a[i]); } else { av = 1; d1 = getVarId(a[i]); } if (isdigit(b[i][0])) { d2 = stoi(b[i]); } else { bv = 1; d2 = getVarId(b[i]); } if (av < bv) swap(av, bv), swap(d1, d2); if (av == 1) { if (bv == 1) { edges[d1].push_back(d2); edges[d2].push_back(d1); } else { owned[d1].push_back(d2); } } else { if (d1 != d2) { cout << "NE\n"; return 0; } } } for (int i = 0; i < m; ++i) { if (dfs(i) == -1) return cout << "NE\n", 0; } cout << "DA"; 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...