Submission #1194411

#TimeUsernameProblemLanguageResultExecution timeMemory
1194411cpdreamerConnecting Supertrees (IOI20_supertrees)C++20
96 / 100
253 ms26404 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define pb push_back #define V vector using namespace std; typedef long long ll; #define all(v) v.begin(), v.end() #define P pair #define F first #define S second V<int>adj[(int)2000]; V<int>comp(2000); V<bool>visited(2000); void dfs(int nd,int s,V<int>&vp){ if(visited[nd]){ return; } vp.pb(nd); visited[nd]=true; comp[nd]=s; for(auto u:adj[nd]){ dfs(u,s,vp); } } int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> answer(n,V<int>(n,0)); for(int i=0;i<n;i++){ comp[i]=i; visited[i]=false; } V<V<int>>C; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]==1 && i!=j){ adj[i].pb(j); } } } for(int i=0;i<n;i++){ V<int>vp; dfs(i,i,vp); if(!vp.empty()){ C.pb(vp); } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(comp[i]==comp[j] && (p[i][j]==0 || p[i][j]==2))return 0; } } V<P<int,V<int>>>a; for(auto u:C){ a.pb({u[0],u}); if(u.size()==1)continue; for(int i=1;i<(int)u.size();i++){ answer[u[0]][u[i]]=1; answer[u[i]][u[0]]=1; } } for(int i=0;i<n;i++){ adj[i].clear(); visited[i]=false; } for(int i=0;i<(int)a.size();i++){ for(int j=0;j<(int)a.size();j++){ if(p[a[i].F][a[j].F]==2){ adj[a[i].F].pb(a[j].F); } } } for(int i=0;i<(int)a.size();i++){ V<int>vp; if(!visited[a[i].F]){ dfs(a[i].F,a[i].F,vp); if(vp.size()==1)continue; if(vp.size()==2)return 0; for(int j=0;j<(int)vp.size();j++){ for(int g=0;g<(int)vp.size();g++){ if(j==g)continue; if(p[vp[j]][vp[g]]!=2)return 0; } } V<P<int,int>>A; for(int j=0;j<(int)vp.size();j++){ for(auto v:a){ if(v.F==vp[j]) { for (auto x: v.S) { A.pb({x, j}); } break; } } } for(int j=0;j<(int)A.size();j++){ for(int g=0;g<(int)A.size();g++){ if(A[j].S!=A[g].S && p[A[j].F][A[g].F]!=2)return 0; } } for(int j=0;j<(int)vp.size()-1;j++){ answer[vp[j]][vp[j+1]]=1; answer[vp[j+1]][vp[j]]=1; } answer[vp[0]][vp[(int)vp.size()-1]]=1; answer[vp[(int)vp.size()-1]][vp[0]]=1; } } build(answer); return 1; }
#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...