제출 #441979

#제출 시각아이디문제언어결과실행 시간메모리
441979julian33슈퍼트리 잇기 (IOI20_supertrees)C++14
40 / 100
262 ms26052 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],par[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<int> line; vector<int> ring; for(int &j:component[i]){ int one=0; for(int k=0;k<n;k++){ if(g[j][k]==1 && j!=k){ one=1; break; } } if(one) line.pb(j); else ring.pb(j); } for(int j=0;j<sz(line)-1;j++){ b[line[j]][line[j+1]]=b[line[j+1]][line[j]]=1; } for(int j=0;j<sz(ring)-1;j++){ b[ring[j]][ring[j+1]]=b[ring[j+1]][ring[j]]=1; } // if(sz(ring)==1){ // return 0; // } if(sz(line) && sz(ring)){ b[line.back()][ring.back()]=b[ring.back()][line.back()]=1; b[ring[0]][line.back()]=b[line.back()][ring[0]]=1; } if(sz(line)==0){ if(sz(ring)==2) return 0; b[ring.back()][ring[0]]=b[ring[0]][ring.back()]=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...