제출 #446640

#제출 시각아이디문제언어결과실행 시간메모리
446640crackersamdjam열쇠 (IOI21_keys)C++17
9 / 100
539 ms124856 KiB
#if !defined(ONLINE_JUDGE) && !defined(LOCAL) // oj.uz #include "keys.h" #endif #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #ifdef LOCAL template<typename T> void pr(T a){std::cerr<<a<<std::endl;} template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);} #else template<typename... Args> void pr(Args... args){} #endif using namespace std; using pii = pair<int, int>; int constexpr MM = 3e5+5; int n, m; vector<int> r; vector<int> adj[MM]; // vector<int> adj2[MM]; int outdeg[MM]; int dfn[MM], low[MM], t, id[MM]; bool ins[MM]; stack<int> stk; vector<int> scc[MM]; set<int> newkeys[MM]; set<int> donekeys[MM]; map<int, vector<int>> to[MM]; // which weakly connected component // this is different from id[], which is scc "root" int par[MM]; int find(int x){ while(x != par[x]) x = par[x], par[x] = par[par[x]]; return x; } void merge(int a, int b){ if(a == b) return; // merges b into a if(size(newkeys[b]) > size(newkeys[a])) swap(newkeys[a], newkeys[b]); for(auto i: newkeys[b]) newkeys[a].insert(i); newkeys[b].clear(); if(size(donekeys[b]) > size(donekeys[a])) swap(donekeys[a], donekeys[b]); for(auto i: donekeys[b]) donekeys[a].insert(i); donekeys[b].clear(); if(size(to[a]) > size(to[b])) swap(to[a], to[b]); for(auto &[i, v]: to[b]){ if(size(v) > size(to[a][i])) swap(to[a][i], v); to[a][i].insert(to[a][i].end(), all(v)); } to[b].clear(); if(size(scc[a]) > size(scc[b])) swap(scc[a], scc[b]); scc[a].insert(scc[a].end(), all(scc[b])); scc[b].clear(); par[find(b)] = find(a); } void dfs(int cur){ dfn[cur] = low[cur] = ++t; stk.push(cur); ins[cur] = 1; for(auto u: adj[cur]){ if(!dfn[u]){ dfs(u); low[cur] = min(low[cur], low[u]); } else if(ins[u]) low[cur] = min(low[cur], dfn[u]); } if(dfn[cur] == low[cur]){ int u = -1; while(u != cur){ u = stk.top(); stk.pop(); ins[u] = 0; id[u] = cur; merge(cur, u); } } } vector<int> find_reachable(vector<int> _r, vector<int> a, vector<int> b, vector<int> c){ r = move(_r); n = size(r); m = size(a); vector<int> res(n); for(int i = 0; i < m; i++){ if(c[i] == r[a[i]]){ adj[a[i]].emplace_back(b[i]); // pr("edge", a[i], b[i]); } else{ to[a[i]][c[i]].emplace_back(b[i]); } if(c[i] == r[b[i]]){ adj[b[i]].emplace_back(a[i]); // pr("edge", a[i], b[i]); } else{ to[b[i]][c[i]].emplace_back(a[i]); } } for(int i = 0; i < n; i++){ par[i] = i; newkeys[i].insert(r[i]); scc[i].emplace_back(i); } for(int i = 0; i < n; i++){ if(!dfn[i]){ dfs(i); } } for(int i = 0; i < n; i++){ for(int j: adj[i]){ if(id[i] != id[j]){ // adj2[id[i]].emplace_back(id[j]); outdeg[id[i]] = 1; } } } // each scc root... vector<int> roots; for(int i = 0; i < n; i++){ // if(!size(adj2[i])){ if(!outdeg[i]){ roots.emplace_back(i); pr("add rt", i); } } for(auto rt: roots){ while(size(newkeys[rt])){ auto i = *newkeys[rt].begin(); newkeys[rt].erase(i); if(donekeys[rt].count(i)) continue; donekeys[rt].insert(i); for(auto u: to[rt][i]){ if(find(u) == find(rt)){ merge(rt, u); } else{ merge(u, rt); break; } } } } int ans = 1e9; for(auto rt : roots){ if(find(rt) == rt){ int s = size(scc[rt]); pr("check sz", rt, s); if(s < ans){ ans = s; } } } for(auto rt : roots){ if(find(rt) == rt){ int s = size(scc[rt]); if(s == ans){ pr("scc", rt); for(auto j: scc[rt]){ pr("j", j); res[j] = 1; } } } } return res; } #ifdef LOCAL namespace me{ void go(){ int n, m; cin>>n>>m; vector<int> r(n), a(m), b(m), c(m); for(int i = 0; i < n; i++) cin>>r[i]; for(int i = 0; i < m; i++){ cin>>a[i]>>b[i]>>c[i]; } auto res = find_reachable(r, a, b, c); for(int i = 0; i < size(res); i++) cout<<res[i]<<' '; } } int main(){ me::go(); } #endif
#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...