Submission #752523

#TimeUsernameProblemLanguageResultExecution timeMemory
7525231binKeys (IOI21_keys)C++17
9 / 100
607 ms101664 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 3e5 + 5; int n, m, par[NMAX], dfsn[NMAX], fin[NMAX], sz[NMAX], bad[NMAX], t, from[NMAX]; vector<int> E[NMAX]; set<int> K[NMAX]; map<int, vector<int>> mp[NMAX]; int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);} void Union(int a, int b){ if(K[a].size() + mp[a].size() < K[b].size() + mp[b].size()) swap(K[a], K[b]), swap(mp[a], mp[b]); for(auto&[k, v] : mp[b]){ if(K[a].find(k) == K[a].end()) { if(mp[a][k].size() < v.size()) swap(mp[a][k], v); for(auto&y : v) mp[a][k].emplace_back(y); } else{ if(E[a].size() < v.size()) swap(E[a], v); for(auto& y : v) E[a].emplace_back(y); } } for(auto& k : K[b]) K[a].emplace(k); if(E[a].size() < E[b].size()) swap(E[a], E[b]); for(auto& e : E[b]) E[a].emplace_back(e); E[b].clear(); sz[a] += sz[b]; par[b] = a; bad[a] |= bad[b]; return; } void dfs(int x){ dfsn[x] = ++t; while(E[x].size()){ x = find(x); int nx = find(E[x].back()); E[x].pop_back(); if(x == nx) continue; if(!dfsn[nx]){ from[nx] = x; dfs(nx); } else if(!fin[nx]){ for(int i = x; i != nx; i = from[i]) Union(nx, i); } if(find(nx) != find(x)) bad[x] = 1; } fin[x] = 1; return; } vector<int> find_reachable(vector<int>r, vector<int> u, vector<int> v, vector<int> c){ n = r.size(); m = u.size(); auto add_edge = [&](int& a, int& b, int& c){ if(r[a] == c) E[a].emplace_back(b); else mp[a][c].emplace_back(b); }; for(int i = 0; i < m; i++){ add_edge(u[i], v[i], c[i]); add_edge(v[i], u[i], c[i]); } memset(par, -1, sizeof(par)); for(int i = 0; i < n; i++) sz[i] = 1, K[i].emplace(r[i]); for(int i = 0; i < n; i++) if(!dfsn[i]) dfs(i); vector<int> res(n, 0); int mn = n + 1; for(int i = 0; i < n; i++) if(!bad[find(i)]) mn = min(mn, sz[find(i)]); for(int i = 0; i < n; i++) if(!bad[find(i)] && sz[find(i)] == mn) res[i] = 1; return res; } /* int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> r(n), u(m), v(m), c(m); for(auto& i : r) cin >> i; for(auto& i : u) cin >> i; for(auto& i : v) cin >> i; for(auto& i : c) cin >> i; vector<int> res = find_reachable(r, u, v, c); for(int i = 0; i < n; i++) cout << res[i] << ' '; return 0; } */ /* test1 4 5 0 1 1 2 0 0 1 1 3 1 2 2 3 1 0 0 1 0 2 test2 7 10 0 1 1 2 2 1 2 0 0 1 1 2 3 3 4 4 5 1 2 2 3 3 4 5 5 6 6 0 0 1 0 0 1 2 0 2 1 test3 3 1 0 0 0 0 1 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...