Submission #439856

#TimeUsernameProblemLanguageResultExecution timeMemory
439856adamjinweiConnecting Supertrees (IOI20_supertrees)C++14
21 / 100
455 ms33804 KiB
#include <bits/stdc++.h> #include "supertrees.h" #define inf 1000000007 #define mod 1000000007 #define rnd() rand_num() #define bigrnd() dis(rand_num) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") //#define int long long using namespace std; unsigned sed=std::chrono::system_clock::now().time_since_epoch().count(); mt19937 rand_num(sed); uniform_int_distribution<long long> dis(0,inf); template <typename T> void read(T &x){ x=0;char ch=getchar();int fh=1; while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();} while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); x*=fh; } template <typename T> void write(T x) { if (x<0) x=-x,putchar('-'); if (x>9) write(x/10); putchar(x%10+'0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n; int fa[1005]; int g[1005][1005]; int fa1[1005]; vector<int> vec[1005]; int fnd(int x) { if(fa[x]!=x) fa[x]=fnd(fa[x]); return fa[x]; } int fnd1(int x) { if(fa1[x]!=x) fa1[x]=fnd1(fa1[x]); return fa1[x]; } int construct(vector<vector<int>> p) { n=p.size(); for(int i=0;i<n;++i) fa[i]=i; for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(p[i][j]==3) return 0; else if(p[i][j]!=0) fa[fnd(i)]=fnd(j); for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(p[i][j]==0&&fnd(i)==fnd(j)) return 0; for(int i=0;i<n;++i) fa[i]=i; for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(p[i][j]==1) fa[fnd(i)]=fnd(j); for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(p[i][j]==2&&fnd(i)==fnd(j)) return 0; for(int i=0;i<n;++i) fa1[i]=i; bool flag=false; for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(p[i][j]==2) { flag=true; fa1[fnd1(fnd(i))]=fnd1(fnd(j)); } for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(p[i][j]==2) { vec[fnd1(fnd(i))].push_back(fnd(i)); vec[fnd1(fnd(j))].push_back(fnd(j)); } for(int i=0;i<n;++i) if(fnd(i)==i) { sort(vec[fnd1(i)].begin(),vec[fnd1(i)].end()); vec[fnd1(i)].erase(unique(vec[fnd1(i)].begin(),vec[fnd1(i)].end()),vec[fnd1(i)].end()); if(flag&&vec[fnd1(i)].size()<3) return 0; if(flag) { for(int j=0;j+1<vec[fnd1(i)].size();++j) g[vec[fnd1(i)][j]][vec[fnd1(i)][j+1]]=g[vec[fnd1(i)][j+1]][vec[fnd1(i)][j]]=1; if(vec[fnd1(i)].size()>1) g[vec[fnd1(i)][0]][vec[fnd1(i)][vec[fnd1(i)].size()-1]]=g[vec[fnd1(i)][vec[fnd1(i)].size()-1]][vec[fnd1(i)][0]]=1; } } for(int i=0;i<n;++i) if(fnd(i)!=i) g[fnd(i)][i]=g[i][fnd(i)]=1; vector<vector<int>> ans; for(int i=0;i<n;++i) { vector<int> tmp; for(int j=0;j<n;++j) tmp.push_back(g[i][j]); ans.push_back(tmp); } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int j=0;j+1<vec[fnd1(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...