Submission #197538

#TimeUsernameProblemLanguageResultExecution timeMemory
197538WindazzZamjena (COCI18_zamjena)C++17
0 / 70
54 ms34040 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define x first #define y second #define ndl '\n' #define mp make_pair #define mt make_tuple #define pb push_back #define up_b upper_bound #define low_b lower_bound #define sz(x) (int)x.size() #define bit __builtin_popcount #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; using namespace __gnu_pbds; template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef pair<int, ll> pil; typedef pair<ll, int> pli; typedef pair<int, ull> piu; typedef vector<vector<int>> matrix; const ll INF = 1e18 + 123; const ld EPS = 1e-9; const int inf = 1e9 + 123; const int MOD = 1e9 + 7; const int N = 5e5 + 13; const int M = 1e6 + 123; const double pi = acos(-1.0); const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; string a[N], b[N]; map<string, vector<string> > g; map<string, string> num; void dfs(string v){ for (string to : g[v]){ if (num[to].empty()){ num[to] = num[v]; dfs(to); } else if (num[to] != num[v]){ cout << "NO"; exit(0); } } } int main(){ #ifdef KAZAKH freopen("input.txt", "r", stdin); #endif ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i <= 1000; i++){ auto s = to_string(i); num[s] = s; } for (int i = 1; i <= n; i++){ cin >> a[i]; } for (int i = 1; i <= n; i++){ cin >> b[i]; } vector<string> z; for (int i = 1; i <= n; i++){ if (num[a[i]].empty() && num[b[i]].empty()){ g[a[i]].pb(b[i]); g[b[i]].pb(a[i]); continue; } if (num[a[i]].empty()){ num[a[i]] = num[b[i]]; z.pb(a[i]); } if (num[b[i]].empty()){ num[b[i]] = num[a[i]]; z.pb(b[i]); } if (num[a[i]] != num[b[i]]){ cout << "NO"; return 0; } } for (auto p : z){ dfs(p); } cout << "YES"; 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...