제출 #315576

#제출 시각아이디문제언어결과실행 시간메모리
315576tigicha슈퍼트리 잇기 (IOI20_supertrees)C++14
19 / 100
1091 ms30200 KiB
#include "supertrees.h" #include<bits/stdc++.h> using namespace std; int par[1005], ar[1005], a[1005][1005], ans[1005][1005], fix1[1005], n, fix[1005]; vector<int>vec1[1005], vec[1005], v1; vector<vector<int> >answer; int parent(int x){ if(par[x]==x) return x; return par[x]=parent(par[x]); } void dsu(int x, int y){ x=parent(x); y=parent(y); if(x==y) return; if(ar[x]<ar[y]) swap(x, y); par[y]=x; ar[x]+=ar[y]; } void rec(int z){ for(int i=0; i<vec1[z].size(); i++) for(int j=i+1; j<vec1[z].size(); j++) if(a[vec1[z][i]][vec1[z][j]]==1){ vec[vec1[z][i]].push_back(vec1[z][j]); vec[vec1[z][j]].push_back(vec1[z][i]); } v1.clear(); for(int i=0; i<vec1[z].size(); i++){ int x=vec1[z][i]; if(fix[x]) continue; v1.push_back(x); fix1[x]=1; if(!fix[x]) for(int j=0; j<vec[x].size(); i++){ fix[vec[x][j]]=x; ans[x][vec[x][j]]=1; ans[vec[x][j]][x]=1; } } if(v1.size()>1) for(int i=0; i<v1.size(); i++){ ans[v1[i]][v1[(i+1)%v1.size()]]=1; ans[v1[(i+1)%v1.size()]][v1[i]]=1; } } bool check(){ for(int i=1; i<=n; i++){ std::vector<int> v2; for(int j=1; j<=n; j++){ if(i==j) ans[i][i]=0; else{ if(a[i][j]==0 && parent(i)==parent(j)) return 0; if(!fix1[i] && !fix1[j] && a[i][j]==2 && fix[i]==fix[j]) return 0; } v2.push_back(ans[i][j]); } answer.push_back(v2); } return 1; } int construct(std::vector<std::vector<int> > v){ n=v.size(); for(int i=1; i<=n; i++){ par[i]=i; ar[i]=1; } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){ a[i][j]=v[i-1][j-1]; if(a[i][j]==3) return 0; if(a[i][j]!=0) dsu(i, j); } for(int i=1; i<=n; i++) vec1[parent(i)].push_back(i); for(int k=1; k<=n; k++){ rec(k); if(v1.size()==2 && a[v1[0]][v1[1]]==2) return 0; } if(!check()) return 0; build(answer); return 1; }

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'void rec(int)':
supertrees.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<vec1[z].size(); i++)
      |               ~^~~~~~~~~~~~~~~
supertrees.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int j=i+1; j<vec1[z].size(); j++)
      |                 ~^~~~~~~~~~~~~~~
supertrees.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0; i<vec1[z].size(); i++){
      |               ~^~~~~~~~~~~~~~~
supertrees.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j=0; j<vec[x].size(); i++){
      |                ~^~~~~~~~~~~~~~
supertrees.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0; i<v1.size(); i++){
      |               ~^~~~~~~~~~
#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...