제출 #1058861

#제출 시각아이디문제언어결과실행 시간메모리
1058861LittleOrange열쇠 (IOI21_keys)C++17
9 / 100
96 ms34176 KiB
#include <vector> #include<bits/stdc++.h> using namespace std; using ll = int; struct dsu{ ll n; vector<ll> p; dsu(ll N):n(N),p(N,-1){} ll g(ll i){ return p[i]<0?i:p[i]=g(p[i]); } bool e(ll a, ll b){ return g(a)==g(b); } bool m(ll a, ll b){ a = g(a); b = g(b); if(a==b) return false; if(p[a]>p[b]) swap(a,b); p[a]+=p[b]; p[b]=a; return true; } ll sz(ll i){ return -p[g(i)]; } }; std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { ll n = r.size(); ll m = u.size(); std::vector<int> ans(r.size(), 0); /*ll task1 = 1; for(ll i : c) if(i) task1 = 0; if (task1){ ll zc = 0; for(ll i : r){ zc += i==0; } if(zc!=n){ vector<ll> ret(n,0); for(ll i = 0;i<n;i++) ret[i] = r[i]!=0; return ret; } dsu d(n); for(ll i = 0;i<m;i++) d.m(u[i],v[i]); ll mi = n; for(ll i = 0;i<n;i++) mi = min(mi,d.sz(i)); vector<ll> ret(n,0); for(ll i = 0;i<n;i++) ret[i] = d.sz(i)==mi; return ret; }*/ vector<vector<ll>> con(n); for(ll i = 0;i<m;i++){ if (r[u[i]]==c[i]) con[u[i]].push_back(v[i]); if (r[v[i]]==c[i]) con[v[i]].push_back(u[i]); } ll easy = 0; for(auto &o : con) if(o.empty()) easy = 1; if(easy){ for(ll i = 0;i<n;i++) ans[i] = con[i].size()==0; return ans; } vector<ll> bad(n,0),ins(n,0),st; dsu d(n); function<void(ll)> dfs; dfs = [&](ll i){ if(bad[i]) return; ins[i] = 1; st.push_back(i); for(ll j : con[i]){ if (ins[j]){ for(ll x = st.size()-1;st[x]!=j;x--){ d.m(st[x],st[x-1]); } }else{ dfs(j); } } ins[i] = 0; st.pop_back(); bad[i] = 1; }; for(ll i = 0;i<n;i++) dfs(i); vector<ll> ok(n,1); for(ll i = 0;i<n;i++){ for(ll j : con[i]){ if (!d.e(i,j)) ok[d.g(i)] = 0; } } ll mi = n; for(ll i = 0;i<n;i++){ if (ok[d.g(i)]) mi = min(mi,d.sz(i)); } for(ll i = 0;i<n;i++) ans[i] = ok[d.g(i)]&&d.sz(i)==mi; return ans; }
#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...