제출 #598747

#제출 시각아이디문제언어결과실행 시간메모리
598747sofapuden열쇠 (IOI21_keys)C++17
100 / 100
2076 ms271376 KiB
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #include<bits/stdc++.h> using namespace std; struct DSU { int n; vector<int> p; DSU(int _n) : n(_n) { p.resize(n); iota(p.begin(),p.end(),0); } int get(int x){ return x ^ p[x] ? p[x] = get(p[x]) : x; } void unite(int a, int b){ a = get(a), b = get(b); p[a] = b; } }; struct info { unordered_map<int,vector<int>> blo; unordered_set<int> unl; }; vector<info> inf; vector<int> vis; bool step(vector<int> &r, vector<vector<pair<int,int>>> &gr, DSU &d){ bool ok = 0; int n = r.size(); vis.clear(); vis.resize(n,0); queue<pair<int,int>> Q; for(int i = 0; i < n; ++i){ if(i == d.get(i)){ Q.push({i,i}); while(Q.size()){ auto x = Q.front(); Q.pop(); if(x.second != d.get(x.second))continue; if(d.get(x.first) != x.second){ ok = 1; d.unite(x.second,x.first); continue; } if(vis[x.first])continue; vis[x.first] = 1; for(auto y : gr[x.first]){ if(inf[x.second].unl.count(y.second))Q.push({y.first,x.second}); else inf[x.second].blo[y.second].push_back(y.first); } inf[x.second].unl.insert(r[x.first]); for(auto y : inf[x.second].blo[r[x.first]])Q.push({y,x.second}); inf[x.second].blo[r[x.first]].clear(); } } } return ok; } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){ int n = r.size(); int m = u.size(); inf.resize(n); DSU d(n); vector<vector<pair<int,int>>> gr(n); for(int i = 0; i < m; ++i){ gr[u[i]].push_back({v[i],c[i]}); gr[v[i]].push_back({u[i],c[i]}); } while(step(r,gr,d)); vector<int> nsiz(n,0); int mn = n+1; for(int i = 0; i < n; ++i){ if(vis[i])nsiz[d.get(i)]++; } for(int i = 0; i < n; ++i){ mn = min(mn,nsiz[d.get(i)]); } for(int i = 0; i < n; ++i){ if(mn != nsiz[d.get(i)])vis[i] = 0; } return vis; }
#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...