Submission #989779

#TimeUsernameProblemLanguageResultExecution timeMemory
989779RandomUserZamjena (COCI18_zamjena)C++17
70 / 70
66 ms5084 KiB
#include <bits/stdc++.h> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() //#define int long long using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; const double eps = 1e-9; struct DSU { int n, comp; vector<int> par, size; void config(int _n) { n = _n + 1; comp = _n; par.resize(n+1); size.resize(n+1, 1); for(int i=1; i<=n; i++) par[i] = i; } int get(int u) { if(u == par[u]) return u; return par[u] = get(par[u]); } bool uni(int u, int v) { u = get(u), v = get(v); if(u == v) return false; if(size[u] < size[v]) swap(u, v); size[u] += size[v]; par[v] = u; comp--; return true; } int getComp() { return comp; } int getSize(int u) { return size[get(u)]; } bool sameSet(int u, int v) { return get(u) == get(v); } }; bool isNum(string s) { for(char &ch : s) if(ch < '0' || ch > '9') return 0; return 1; } int toNum(string s) { int ans=0, c=1; while(!s.empty()) { char ch = s.back(); s.pop_back(); ans += (ch - '0') * c; c *= 10; } return ans; } int32_t main() { int n, id = 1000; cin >> n; map<string, int> mp; vector<bool> numA(n), numB(n); vector<int> a(n), b(n); set<int> st; for(int i=0; i<n; i++) { string s; cin >> s; if(isNum(s)) { a[i] = toNum(s); numA[i] = 1; st.insert(a[i]); } else { if(mp.count(s)) a[i] = mp[s]; else mp[s] = id++, a[i] = mp[s]; } } for(int i=0; i<n; i++) { string s; cin >> s; if(isNum(s)) { b[i] = toNum(s); numB[i] = 1; st.insert(b[i]); } else { if(mp.count(s)) b[i] = mp[s]; else mp[s] = id++, b[i] = mp[s]; } } for(int i=0; i<n; i++) { if(numA[i] && numB[i] && a[i] != b[i]) { cout << "NE\n"; return 0; } } DSU dsu; dsu.config(52000); for(int i=0; i<n; i++) { if(!numA[i] || !numB[i]) dsu.uni(a[i], b[i]); } set<int> st2; for(auto &x : st) st2.insert(dsu.get(x)); cout << (st.size() == st2.size() ? "DA" : "NE") << '\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...