Submission #254519

#TimeUsernameProblemLanguageResultExecution timeMemory
254519Vladikus004Zamjena (COCI18_zamjena)C++14
70 / 70
162 ms14000 KiB
#include <bits/stdc++.h> #define inf 2e9 #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef long double ld; typedef pair <int, int> pii; const int N = 50000 + 3; int n, cnt, p[2 * N]; string a[N], b[N]; map <string, int> code; vector <string> v; set <string> ms[2 * N]; int is_num(string &s){ return int((s[0] >= '0') && (s[0] <= '9')); } void init(){ for (int i = 0; i < n * 2; i++) p[i] = i; } int get_anc(int x){ if (p[x] == x) return x; return p[x] = get_anc(p[x]); } void unite(int x, int y){ x = get_anc(x); y = get_anc(y); if (x == y) return; if (rand() & 1) swap(x, y); p[x] = y; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL cin >> n; init(); for (int i = 0; i < n; i++) { cin >> a[i]; if (!is_num(a[i])){ if (!code[a[i]]) { code[a[i]] = ++cnt; v.push_back(a[i]); } } } for (int i = 0; i < n; i++) { cin >> b[i]; if (!is_num(b[i])){ if (!code[b[i]]) { code[b[i]] = ++cnt; v.push_back(b[i]); } } } for (int i = 0; i < n; i++){ if (a[i] == b[i]){ continue; } if (is_num(a[i]) + is_num(b[i]) == 2){ if (a[i] != b[i]){ cout << "NE"; return 0; } }else if (is_num(a[i]) + is_num(b[i])){ continue; }else{ unite(code[a[i]] - 1, code[b[i]] - 1); } } for (int i = 0; i < n; i++){ if (!is_num(a[i])){ a[i] = v[get_anc(code[a[i]] - 1)]; } } for (int i = 0; i < n; i++){ if (!is_num(b[i])){ b[i] = v[get_anc(code[b[i]] - 1)]; } } // for (int i = 0; i < n; i++) cout << a[i] << " "; cout << "\n"; // for (int i = 0; i < n; i++) cout << b[i] << " "; cout << "\n"; for (int i = 0; i < n; i++){ if (is_num(a[i]) && !is_num(b[i])){ ms[code[b[i]] - 1].insert(a[i]); if (ms[code[b[i]] - 1].size() > 1){ cout << "NE"; return 0; } }else if (!is_num(a[i]) && is_num(b[i])){ ms[code[a[i]] - 1].insert(b[i]); if (ms[code[a[i]] - 1].size() > 1){ cout << "NE"; return 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...