Submission #487885

#TimeUsernameProblemLanguageResultExecution timeMemory
487885ala2Connecting Supertrees (IOI20_supertrees)C++14
96 / 100
214 ms26168 KiB
#include "supertrees.h" #include <vector> #include<iostream> using namespace std; int pa[1001000]; int sz[1001000]; int root(int x) { while(x!=pa[x]) { pa[x]=pa[pa[x]]; x=pa[x]; } return x; } void unit(int x,int y) { x=root(x); y=root(y); if(x==y) return ; if(sz[x]>sz[y]) { sz[x]+=sz[y]; pa[y]=x; } else { sz[y]+=sz[x]; pa[x]=y; } } vector<int>v[1010]; int vi[1010]; int vis[5][1010][1010]; int construct(vector<vector<int>> p) { int n = p.size(); int bb=0; vector<vector<int>> answer; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); answer.push_back(row); } for(int i=0;i<n;i++) { pa[i]=i; sz[i]=1; } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(p[i][j]==1) { unit(i,j); } } } for(int i=0;i<n;i++) { v[root(i)].push_back(i); } for(int i=0;i<n;i++) { if(i!=root(i)) continue; if(v[i].size()==1) { continue; } for(int j=0;j<v[i].size()-1;j++) { int x=v[i][j]; int y=v[i][j+1]; answer[x][y]=1; answer[y][x]=1; } } for(int i=0;i<n;i++) { if(i!=root(i)) continue; int tow=0; int three=0; vector<int>r; r.push_back(i); vi[root(i)]=1; for(int j=0;j<n;j++) { if(p[i][j]>=2&&!vi[root(j)]) { if(p[i][j]==2) tow=2; else tow=3; r.push_back(root(j)); vi[root(j)]=1; } } // cout<<" "<<r.size()<<endl; if(r.size()==1) continue; if(r.size()==2&&tow==2) bb=1; if(r.size()<=3&&tow==3) bb=1; for(int k=0;k<r.size()-1;k++) { int x=r[k]; int y=r[k+1]; answer[x][y]=1; answer[y][x]=1; } int ss=r.size()-1; answer[r[ss]][r[0]]=1; answer[r[0]][r[ss]]=1; if(tow>2){ answer[r[0]][r[2]]=1; answer[r[2]][r[0]]=1; } for(int ii=0;ii<r.size();ii++) { for(int jj=0;jj<r.size();jj++) { if(ii==jj) continue; vis[tow][r[ii]][r[jj]]=1; vis[tow][r[jj]][r[ii]]=1; } } } for(int i=0;i<n;i++) { answer[i][i]=0; for(int j=0;j<n;j++) { if(i==j) continue; // cout<<vis[i][j]<<" "; if(p[i][j]>=2&&!vis[p[i][j]][root(i)][root(j)]) bb=1; if(p[i][j]<2&&vis[p[i][j]][root(i)][root(j)]) bb=1; if(p[i][j]==1&&root(i)!=root(j)) bb=1; if(root(i)==root(j)&&p[i][j]!=1) bb=1; if(p[i][j]==0&&vis[3][root(i)][root(j)]) bb=1; if(p[i][j]==0&&vis[2][root(i)][root(j)]) bb=1; } } if(bb) return 0; else { build(answer); return 1; } }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int j=0;j<v[i].size()-1;j++)
      |                     ~^~~~~~~~~~~~~~
supertrees.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int k=0;k<r.size()-1;k++)
      |                     ~^~~~~~~~~~~
supertrees.cpp:125:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for(int ii=0;ii<r.size();ii++)
      |                      ~~^~~~~~~~~
supertrees.cpp:127:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             for(int jj=0;jj<r.size();jj++)
      |                          ~~^~~~~~~~~
supertrees.cpp:88:13: warning: unused variable 'three' [-Wunused-variable]
   88 |         int three=0;
      |             ^~~~~
supertrees.cpp:153:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  153 |             if(p[i][j]==0&&vis[3][root(i)][root(j)])
      |             ^~
supertrees.cpp:155:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  155 |                 if(p[i][j]==0&&vis[2][root(i)][root(j)])
      |                 ^~
#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...