Submission #1186536

#TimeUsernameProblemLanguageResultExecution timeMemory
1186536WarinchaiConnecting Supertrees (IOI20_supertrees)C++20
100 / 100
139 ms26168 KiB
#include "supertrees.h" #include <vector> #include<bits/stdc++.h> using namespace std; int N; vector<vector<int>>adj; int pa[1005]; int fp(int a){return pa[a]==a?a:pa[a]=fp(pa[a]);} void un(int a,int b){pa[fp(b)]=fp(a);} int have1[1005]; int have2[1005]; int have3[1005]; int vis1[1005]; int vis2[1005]; int vis3[1005]; int cant=0; vector<vector<int>> answer; void build1(int u){ //cerr<<"build1:"<<u<<"\n"; vector<int>node; node.push_back(u); vis1[u]=1; for(int i=0;i<N;i++)if(i!=u&&adj[u][i]==1){ vis1[i]=1; node.push_back(i); un(i,u); } //for(auto x:node)cerr<<x<<" "; //cerr<<"\n"; for(int i=0;i<node.size()-1;i++){ int x=node[i],y=node[i+1]; answer[x][y]=1,answer[y][x]=1; } } void build2(int u){ //cerr<<"build2:"<<u<<"\n"; vector<int>node; node.push_back(u); vis2[u]=1; for(int i=0;i<N;i++){ int x=fp(i); if(vis2[x])continue; if(x!=u&&adj[u][x]==2){ vis2[x]=1; node.push_back(x); } } if(node.size()<3)cant=1; for(int i=0;i<node.size();i++){ int x=node[i],y=node[(i+1)%node.size()]; answer[x][y]=1,answer[y][x]=1; } } void build3(int u){ //bruhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh how am i so dumb cant=1; vector<int>node; node.push_back(u); vis3[u]=1; if(vis2[u])cant=1; for(int i=0;i<N;i++){ int x=fp(i); if(vis3[x])continue; if(x!=u&&adj[u][x]==3){ vis3[x]=1; node.push_back(x); if(vis2[x])cant=1; } } if(node.size()<4){ cant=1; return; } for(int i=0;i<node.size();i++){ int x=node[i],y=node[(i+1)%node.size()]; answer[x][y]=1,answer[y][x]=1; } answer[node[0]][node[2]]=answer[node[2]][node[0]]=1; } void check_con(){ for(int i=0;i<N;i++)pa[i]=i; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(adj[i][j]>0)un(i,j); } } for(int i=0;i<N;i++)for(int j=0;j<N;j++){ if(i==j)continue; int x=(adj[i][j]>0); int y=(fp(i)==fp(j)); if(x!=y)cant=1; } } int construct(std::vector<std::vector<int>> p) { N = p.size(); for (int i = 0; i < N; i++) { vector<int> row; row.resize(N); answer.push_back(row); } adj=p; for(int i=0;i<N;i++)pa[i]=i; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ int x=p[i][j]; if(x==1)have1[i]=1; else if(x==2)have2[i]=1; else if(x==3)have3[i]=1; } if(have2[i]&&have3[i])cant=1; } for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(adj[i][j]!=adj[j][i]||(i==j&&adj[i][j]!=1))cant=1; for(int i=0;i<N;i++)if(have1[i]&&vis1[i]==0)build1(i); for(int i=0;i<N;i++){ int x=fp(i); if(have2[x]&&vis2[x]==0)build2(x); } for(int i=0;i<N;i++){ int x=fp(i); if(have3[x]&&vis3[x]==0)build3(x); } check_con(); if(cant)return 0; 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...