제출 #1238104

#제출 시각아이디문제언어결과실행 시간메모리
1238104i_love_mriti슈퍼트리 잇기 (IOI20_supertrees)C++20
100 / 100
148 ms38080 KiB
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define ll long long #define show(n) cout<<n<<'\n' #define all(v) v.begin(), v.end() #define pb push_back #define fi first #define se second const int mxN = 2005; vector<int> adj[mxN]; vector<vector<int>> ways(mxN,vector<int>(mxN,0)); bool vis[mxN]; /*vector<vector<int>> nways(mxN,vector<int>(mxN,0));*/ struct DSU{ vector<int> sz,par; void init(int n){ sz.resize(n,1); par.resize(n); for(int i=1;i<n;++i) par[i]=i; } int findPar(int u){ if(par[u]==u) return u; return par[u]=findPar(par[u]); } void unite(int u,int v){ int upar=findPar(u); int vpar=findPar(v); if(upar==vpar) return; if(sz[upar]>sz[vpar]){ par[vpar]=upar; sz[upar]+=sz[vpar]; }else{ par[upar]=vpar; sz[vpar]+=sz[upar]; } } bool same(int u,int v){ return findPar(u)==findPar(v); } } ds; void dfs(int u,int lead){ ++ways[lead][u]; vis[u]=1; for(auto it:adj[u]){ if(!vis[it]) dfs(it,lead); } vis[u]=0; } /*void dfs2(int u,int lead){ ++nways[lead][u]; vis[u]=1; for(auto it:adj[u]){ if(!vis[it]) dfs(it,lead); } vis[u]=0; }*/ /* void build(vector<vector<int>> cadj){ int n=cadj.size(); for(int i=0;i<n;++i){ dfs2(i,i); for(int j=0;j<n;++j){ vis[j]=0; } } for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ cout<<ways[i][j]<<" "; }cout<<endl; } } */ int construct(vector<vector<int>> p){ int n=p.size(); ds.init(n+6); vector<vector<int>> current_adj(n,vector<int>(n,0)); for(int i=0;i<n;++i){ vector<int> one_way={i}; for(int j=0;j<n;++j){ if(!ds.same(i,j)&&p[i][j]==1){ ds.unite(i,j); current_adj[one_way.back()][j]=1; current_adj[j][one_way.back()]=1; one_way.pb(j); } } } for(int i=0;i<n;++i){ vector<int> two_way={i}; for(int j=0;j<n;++j){ ways[i][j]=0; if(!ds.same(i,j)&&p[i][j]==2){ ds.unite(i,j); current_adj[two_way.back()][j]=1; current_adj[j][two_way.back()]=1; two_way.pb(j); } } if(two_way.size()>1){ current_adj[two_way.back()][i]=1; current_adj[i][two_way.back()]=1; } } for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ if(current_adj[i][j]){ adj[i].pb(j); adj[j].pb(i); } } } for(int i=0;i<n;++i){ for(int j=0;j<n;++j) vis[j]=0; dfs(i,i); } for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ if(ways[i][j]!=p[i][j]) return 0; } } build(current_adj); return 1; } /* int main() { #ifndef ONLINE_JUDGE freopen("input.in","r",stdin); freopen("output.out","w",stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,u,v;cin>>n>>m; for(int i=0;i<m;++i){ cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } ways.resize(n,vector<int>(n,0)); for(int i=0;i<n;++i){ dfs(i,i); } for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ cout<<ways[i][j]<<" "; }cout<<endl; } construct(ways); return 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...
#Verdict Execution timeMemoryGrader output
Fetching results...