Submission #1264676

#TimeUsernameProblemLanguageResultExecution timeMemory
1264676uzukishinobuConnecting Supertrees (IOI20_supertrees)C++20
Compilation error
0 ms0 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int a; vector <vector<int>> ans,z; struct dsu{ int par[1000005]; set<int> sz[10005]; int tplt=0; void init(){ tplt=0; for (int i=0;i<=a;i++){ par[i]=i; sz[i].clear(); sz[i].insert(i); } } int find(int u){ if (par[u]==u){ return u; } return par[u]=find(par[u]); } bool join(int x,int y){ x=find(x); y=find(y); if (x==y){ return false; } if (sz[x].size()<sz[y].size()){ swap(x,y); } for (auto p:sz[y]){ sz[x].insert(p); } par[y]=x; tplt--; return true; } void off(){ tplt=0; } void on(int n){ par[n]=n; sz[n].clear(); sz[n].insert(n); tplt++; } }; dsu d,d1; vector <int> v; bool check=true; void query(){ set<int> s; d1.off(); for (int i=0;i<v.size();i++){ // cout << v[i] << " "; d1.on(v[i]); for (int j=i;j<v.size();j++){ s.insert(z[v[i]][v[j]]); } } // cout << "\n"; if (s.size()>2){ check=false; return; } // cout << "ok" << "\n"; int p=*s.rbegin(); for (int i=0;i<v.size();i++){ for (int j=i+1;j<v.size();j++){ if (z[v[i]][v[j]]==1){ if (d1.join(v[i],v[j])){ ans[v[i]][v[j]]=ans[v[j]][v[i]]=1; } } } } // cout << d1.tplt << " " << p << "\n"; if (s.size()==1){ return; } // cout << d1.tplt << "\n"; if (d1.tplt<=p){ check=false; return; } if (p==3 && tplt>4){ check=false; return; } // cout << "ok" << "\n"; vector <int> v1; for (int i=0;i<v.size();i++){ if (d1.find(v[i])==v[i]){ v1.push_back(v[i]); } } for (int i=0;i+1<v1.size();i++){ ans[v1[i]][v1[i+1]]=ans[v1[i+1]][v1[i]]=1; d1.join(v1[i],v1[i+1]); } ans[v1[0]][v1[v1.size()-1]]=ans[v1[v1.size()-1]][v1[0]]=1; if (p==3){ ans[v1[1]][v1[v1.size()-1]]=ans[v1[v1.size()-1]][v1[1]]=1; } // cout << "ok" << "\n"; } int construct(vector<vector<int>> p) { a = p.size(); ans.resize(a,vector<int>(a)); z=p; d.init(); int sl1=0; for (int i=0;i<a;i++){ for (int j=0;j<a;j++){ if (p[i][j]>0){ d.join(i,j); } if (p[i][j]==1){ sl1++; } } } // cerr << "ok" << "\n"; for (int i=0;i<a;i++){ if (i==d.find(i)){ for (auto p:d.sz[i]){ v.push_back(p); } query(); v.clear(); if (check==false){ return 0; break; } } // cerr << i << "\n"; } cerr << sl1 << "\n"; if (check){ build(ans); return 1; }else{ } }

Compilation message (stderr)

supertrees.cpp: In function 'void query()':
supertrees.cpp:89:17: error: 'tplt' was not declared in this scope
   89 |     if (p==3 && tplt>4){
      |                 ^~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:149:1: warning: control reaches end of non-void function [-Wreturn-type]
  149 | }
      | ^