제출 #441993

#제출 시각아이디문제언어결과실행 시간메모리
441993julian33슈퍼트리 잇기 (IOI20_supertrees)C++14
40 / 100
265 ms26208 KiB
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define FOR(i,j,n) for(int i=j;i<n;i++) #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} // void build(vector<vector<int>> b){ // int n=sz(b); // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // cout<<b[i][j]<<" "; // } // cout<<"\n"; // } // } const int mxN=1e3+5; int uf[mxN],seen[mxN]; vector<int> component[mxN]; vector<vector<int>> g; int find(int x){return uf[x]<0?x:uf[x]=find(uf[x]);} bool same(int x,int y){return find(x)==find(y);} void unite(int x,int y){ x=find(x); y=find(y); if(x==y) return; if(uf[x]>uf[y]) swap(x,y); uf[x]+=uf[y]; uf[y]=x; } int construct(vector<vector<int>> p){ g=p; memset(uf,-1,sizeof(uf)); int n=sz(p); vector<vector<int>> b; b.resize(n); for(auto &u:b) u.resize(n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(g[i][j]){ unite(i,j); } } } for(int i=0;i<n;i++){ component[find(i)].pb(i); for(int j=0;j<n;j++){ if(!g[i][j] && same(i,j)) return 0; } } for(int i=0;i<n;i++){ //u pretty much have one line graph and one ring if(sz(component[i])<=1) continue; vector<vector<int>> line; vector<int> ring; for(int &j:component[i]){ if(seen[j]) continue; vector<int> one={j}; for(int k=0;k<n;k++){ if(g[j][k]==1 && j!=k){ one.pb(k); seen[k]=1; } } if(sz(one)==1) ring.pb(j); else line.pb(one); } if(sz(line)==0){ if(sz(ring)==2) return 0; for(int j=0;j<sz(ring);j++){ b[ring[j]][ring[(j+1)%sz(ring)]]=b[ring[(j+1)%sz(ring)]][ring[j]]=1; } } else{ for(int j=0;j<sz(ring)-1;j++){ b[ring[j]][ring[j+1]]=b[ring[j+1]][ring[j]]=1; } for(auto u:line){ for(int j=0;j<sz(u)-1;j++){ b[u[j]][u[j+1]]=b[u[j+1]][u[j]]=1; } } for(int j=0;j<sz(line)-1;j++){ b[line[j][0]][line[j+1][0]]=b[line[j+1][0]][line[j][0]]=1; } if(sz(ring)){ b[line.back()[0]][ring.back()]=b[ring.back()][line.back()[0]]=1; b[line[0][0]][ring[0]]=b[ring[0]][line[0][0]]=1; } } } build(b); 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...