Submission #1193497

#TimeUsernameProblemLanguageResultExecution timeMemory
1193497simona1230Connecting Supertrees (IOI20_supertrees)C++20
19 / 100
128 ms30968 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int a[1024][1024]; int l[1024],s[1024]; int fl(int i) { if(i==l[i])return i; return l[i]=fl(l[i]); } void unite(int i,int j) { int li=fl(i); int lj=fl(j); if(li!=lj) { l[li]=lj; s[lj]+=s[li]; } } vector<int> v[200001]; vector<vector<int> > ans; int construct(std::vector<std::vector<int>> p) { int n=p.size(); for(int i=0;i<n;i++) { l[i]=i; s[i]=1; } for(int i=0;i<n;i++) { ans.push_back({}); for(int j=0;j<n;j++) { ans[i].push_back(0); a[i][j]=p[i][j]; if(a[i][j]!=0) { //cout<<"+ "<<i<<" "<<j<<endl; unite(i,j); } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(a[i][j]==0) { //cout<<i<<" "<<j<<endl; int li=fl(i); int lj=fl(j); if(li==lj)return 0; } } } for(int i=0;i<n;i++) { int li=fl(i); v[li].push_back(i); } for(int i=0;i<n;i++) { if(v[i].size()<=1)continue; if(v[i].size()==2)return 0; for(int j=0;j<v[i].size()-1;j++) { ans[v[i][j]][v[i][j+1]]=ans[v[i][j+1]][v[i][j]]=1; } if(p[v[i][0]][v[i][1]]==2) ans[v[i][0]][v[i][v[i].size()-1]]=ans[v[i][v[i].size()-1]][v[i][0]]=1; } build(ans); return 1; }
#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...