Submission #1114829

#TimeUsernameProblemLanguageResultExecution timeMemory
1114829kokoueConnecting Supertrees (IOI20_supertrees)C++14
11 / 100
161 ms22092 KiB
#include<bits/stdc++.h> #include "supertrees.h" #define maxn 1010 #define f first #define s second using namespace std; int is[maxn]; vector<pair<int,int>> comp[maxn]; int par[maxn]; int findd(int u) { if(par[u]==-1) return u; return par[u]=findd(par[u]); } void unite(int u,int v) { u=findd(u); v=findd(v); if(v==u) return; if(comp[u].size()<comp[v].size()) swap(u,v); for(auto e:comp[v]) comp[u].push_back(e); par[v]=u; comp[v].clear(); } vector<vector<int>> d; int construct(vector<vector<int>> p) { int n=p.size(); for(int i=0;i<n;i++) { par[i]=-1; int cntr=0; vector<int> dumbbb(n,0); d.push_back(dumbbb); for(auto e:p[i]) { if(e==1) cntr++; } is[i]=1; if(cntr==1) is[i]=2; comp[i].push_back({is[i],i}); } for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(p[i][j]) unite(i,j); } } for(int i=0;i<n;i++) { if(comp[i].size()==0 || comp[i].size()==1) continue; // printf("for %d is %d\n",i,comp[i].size()); sort(comp[i].begin(),comp[i].end()); // reverse(comp[i].begin(),comp[i].end()); int prev=-1; int last=-1; // printf("for %d: \n"); for(auto e:comp[i]) { // printf(" {%d,%d}, ",e.f,e.s); if(e.f==1) last=e.s; if(prev==-1) { prev=e.s; continue; } d[prev][e.s]=1; d[e.s][prev]=1; } if(comp[i][comp[i].size()-1].f==1) continue; if(last==-1) { d[comp[i][comp[i].size()-1].s] [comp[i][0].s]=1; d[comp[i][0].s] [comp[i][comp[i].size()-1].s]=1; } else { d[comp[i][comp[i].size()-1].s] [last]=1; d[last] [comp[i][comp[i].size()-1].s]=1; } } build(d); 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...