| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1053123 | epicci23 | Keys (IOI21_keys) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 3e5 + 5;
struct DSU{
vector<int> par,sub;
DSU(int g){
par.assign(g+5,0);
sub.assign(g+5,1);
iota(all(par),0);
}
int find(int a){
if(par[a]==a) return a;
return par[a]=find(par[a]);
}
bool merge(int a,int b){
a=find(a),b=find(b);
if(a==b) return 0;
if(sub[a]>sub[b]) swap(a,b);
sub[b]+=sub[a];
par[a]=b;
return 1;
}
};
DSU dsu(N);
int n,m;
bitset<30> col[N];
vector<array<int,3>> edges;
vector<int> v[N],v2[N];
vector<int> vis,topo,scc;
void build(){
for(int i=0;i<n;i++) v[i].clear(),v2[i].clear();
for(auto x:edges){
if(col[x[0]][x[2]]){
//cout << "edge: " << x[0] << ' ' << x[1] << '\n';
v[x[0]].push_back(x[1]);
v2[x[1]].push_back(x[0]);
}
if(col[x[1]][x[2]]){
//cout << "edge: " << x[1] << ' ' << x[0] << '\n';
v[x[1]].push_back(x[0]);
v2[x[0]].push_back(x[1]);
}
}
}
void dfs(int c,int t){
if(vis[c] || dsu.find(c)!=c) return;
vis[c]=1;
if(t){
for(int x:v[c]) dfs(x,t);
topo.push_back(c);
}
else{
for(int x:v2[c]) dfs(x,t);
scc.push_back(c);
}
}
vector<vector<int>> find_scc(){
topo.clear();
vis.assign(n+5,0);
for(int i=0;i<n;i++) dfs(i,1);
vector<vector<int>> res;
vis.assign(n+5,0);
reverse(all(topo));
for(int x:topo){
if(vis[x]) continue;
scc.clear();
dfs(x,0);
res.push_back(scc);
}
return res;
}
vector<int> find_reachable(vector<int> r, vector<int> git, vector<int> gel, vector<int> renk) {
vector<int> ans(sz(r),-1);
n=sz(r),m=sz(git);
for(int i=0;i<n;i++) col[i][r[i]]=1;
for(int i=0;i<m;i++){
int a=git[i],b=gel[i],c=renk[i];
edges.push_back({a,b,c});
}
while(1){
build();
auto res=find_scc();
bool ok=1;
for(vector<int> x:res) if(sz(x)>1) ok=0;
if(ok) break;
for(vector<int> x:res){
if(sz(x)==1) continue;
int p=sz(x);
for(int i=0;i<p-1;i++){
if(!dsu.merge(x[i],x.back())) continue;
//if(sz(col[x[i]])>sz(col[x.back()])) swap(x[i],x[p-1]);
for(int j=0;j<30;j++) col[x[p-1]][j]|=col[x[i]][j];
}
if(dsu.find(x[p-1])!=x[p-1]) swap(col[x[p-1]],col[dsu.find(x[p-1])]);
}
vector<array<int,3>> new_edges;
for(auto x:edges){
if(dsu.find(x[0])==dsu.find(x[1])) continue;
new_edges.push_back({dsu.find(x[0]),dsu.find(x[1]),x[2]});
}
edges=new_edges;
}
int mini=(int)1e9+5;
for(int i=0;i<n;i++){
if(!v[dsu.find(i)].empty()){
ans[i]=0;
continue;
}
mini=min(mini,dsu.sub[dsu.find(i)]);
}
for(int i=0;i<n;i++){
if(ans[i]!=-1) continue;
if(mini==dsu.sub[dsu.find(i)]) ans[i]=1;
else ans[i]=0;
}
return ans;
}
/*void _(){
cin >> n >> m;
for(int i=1;i<=n;i++){
int a;cin >> a;
col[i].insert(a);
}
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
edges.push_back({a,b,c});
}
while(1){
build();
auto res=find_scc();
bool ok=1;
for(vector<int> x:res) if(sz(x)>1) ok=0;
if(ok) break;
for(vector<int> x:res){
if(sz(x)==1) continue;
int p=sz(x);
for(int i=0;i<p-1;i++){
if(!dsu.merge(x[i],x.back())) continue;
if(sz(col[x[i]])>sz(col[x.back()])) swap(x[i],x[p-1]);
for(int u:col[x[i]]) col[x[p-1]].insert(u);
}
if(dsu.find(x[p-1])!=x[p-1]) swap(col[x[p-1]],col[dsu.find(x[p-1])]);
}
vector<array<int,3>> new_edges;
for(auto x:edges){
if(dsu.find(x[0])==dsu.find(x[1])) continue;
new_edges.push_back({dsu.find(x[0]),dsu.find(x[1]),x[2]});
}
edges=new_edges;
}
vector<int> ans(n+5,-1);
int mini=(int)1e9+5;
for(int i=1;i<=n;i++){
if(!v[dsu.find(i)].empty()){
ans[i]=0;
continue;
}
mini=min(mini,dsu.sub[dsu.find(i)]);
}
for(int i=1;i<=n;i++){
if(ans[i]!=-1) continue;
if(mini==dsu.sub[dsu.find(i)]) ans[i]=1;
else ans[i]=0;
}
for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n];
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/