Submission #301500

#TimeUsernameProblemLanguageResultExecution timeMemory
301500qiangbaoConnecting Supertrees (IOI20_supertrees)C++14
100 / 100
254 ms26236 KiB
#include <iostream> #include <vector> #include "supertrees.h" #define pb push_back using namespace std; int n; vector<vector<int> > a; int vis[1001], vis2[1001]; vector<int> belong; int gp[1001], gplwch[1001]; vector<int> gpl; int fans=1; vector<int> plamt; vector<vector<int> > ans; void dfs(int x) { int i; vis[x]=1, belong.pb(x); for(i=0;i<n;i++) if(a[x][i] && !vis[i]) vis[i]=1, dfs(i); } void wk2() { int i, j; for(i=0;i<belong.size();i++){ int f=belong[i]; if(!vis2[f]){ vis2[f]=true; gp[f]=i, gpl.pb(f), gplwch[i]=f; for(j=0;j<n;j++) if(a[f][j]==1) gp[j]=i, vis2[j]=true; } } // circle if(gpl.size()>=3){ for(i=0;i<gpl.size();i++) ans[gpl[i]][gpl[(i+1)%gpl.size()]]=ans[gpl[(i+1)%gpl.size()]][gpl[i]]=1; } if(gpl.size()==2) fans=0; for(i=0;i<belong.size();i++){ int f=belong[i], f2=gp[f]; if(gplwch[f2]!=f) ans[f][gplwch[f2]]=ans[gplwch[f2]][f]=1; } } void ck() { int i, j; for(i=0;i<belong.size();i++) for(j=i+1;j<belong.size();j++){ int f=belong[i], f2=belong[j]; if((a[f][f2]==1 && gp[f]!=gp[f2]) || (a[f][f2]==2 && gp[f]==gp[f2]) || a[f][f2]==0) fans=0; } } void wk() { int i; for(i=0;i<n;i++) if(!vis[i]){ belong.clear(); gpl.clear(); dfs(i); wk2(); ck(); } } int construct(vector<vector<int> > p) { int three=0; int i, j; a=p; n=p.size(); for(i=0;i<n;i++) plamt.pb(0); for(i=0;i<n;i++) ans.pb(plamt); for(i=0;i<n;i++) for(j=0;j<n;j++) if(a[i][j]==3) three=1; if(three) fans=0; else wk(); if(fans) build(ans); return fans; } //int main() //{ // construct({{1, 2, 0}, {2, 1, 2}, {0, 2, 1}}); // // return 0; //}

Compilation message (stderr)

supertrees.cpp: In function 'void wk2()':
supertrees.cpp:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(i=0;i<belong.size();i++){
      |             ~^~~~~~~~~~~~~~
supertrees.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(i=0;i<gpl.size();i++)
      |                 ~^~~~~~~~~~~
supertrees.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(i=0;i<belong.size();i++){
      |             ~^~~~~~~~~~~~~~
supertrees.cpp: In function 'void ck()':
supertrees.cpp:63:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(i=0;i<belong.size();i++)
      |             ~^~~~~~~~~~~~~~
supertrees.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(j=i+1;j<belong.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...