Submission #1013205

#TimeUsernameProblemLanguageResultExecution timeMemory
1013205LuvidiConnecting Supertrees (IOI20_supertrees)C++17
40 / 100
170 ms24400 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int par[1000],sz[1000]; vector<vector<int>> ans; int rep(int x){ while(x!=par[x])x=par[x]; return x; } void join(int x,int y){ x=rep(x);y=rep(y); if(x==y)return; if(sz[x]>sz[y])swap(x,y); par[x]=y; sz[y]+=sz[x]; } void edge(int x,int y){ ans[x][y]=1; ans[y][x]=1; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); for(int i=0;i<n;i++){ par[i]=i; sz[i]=1; } for (int i=0;i<n;i++){ vector<int> row; row.resize(n); ans.push_back(row); } bool s2=1,s3=1; for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(p[i][j]){ s2&=p[i][j]==1; s3&=p[i][j]==2; join(i,j); } } } for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(p[i][j]==0){ if(rep(i)==rep(j))return 0; }else{ if(rep(i)!=rep(j))return 0; } } } vector<int> v[n]; for(int i=0;i<n;i++)v[rep(i)].push_back(i); for(int i=0;i<n;i++)if(v[i].size()>1){ if(s2){ for(int j=0;j+1<v[i].size();j++){ edge(v[i][j],v[i][j+1]); } }else{ if(v[i].size()==2)return 0; for(int j=0;j+1<v[i].size();j++){ edge(v[i][j],v[i][j+1]); } edge(v[i][0],v[i].back()); } } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for(int j=0;j+1<v[i].size();j++){
      |                ~~~^~~~~~~~~~~~
supertrees.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int j=0;j+1<v[i].size();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...