Submission #1197662

#TimeUsernameProblemLanguageResultExecution timeMemory
1197662ivazivaConnecting Supertrees (IOI20_supertrees)C++20
11 / 100
116 ms21960 KiB
#include <bits/stdc++.h> #include <vector> #include "supertrees.h" using namespace std; #define MAXN 1001 int N; vector<vector<int>> adj; int parent[MAXN],siz[MAXN]; set<int> components[2]; vector<int> korenovi; int get(int node) { if (parent[node]==node) return node; return get(parent[node]); } int construct(std::vector<std::vector<int>> p) { N=p.size();adj.resize(N); for (int node=0;node<N;node++) {parent[node]=node;siz[node]=1;adj[node].resize(N);} for (int node1=0;node1<N;node1++) { for (int node2=0;node2<N;node2++) { if (p[node1][node2]==3) return 0; if (p[node1][node2]!=p[node2][node1]) return 0; if (p[node1][node2]==2 or node1==node2) continue; int koren1=get(node1),koren2=get(node2); if (koren1==koren2) continue; if (siz[koren1]<siz[koren2]) swap(koren1,koren2); parent[koren2]=koren1;siz[koren1]+=siz[koren2]; adj[koren1][koren2]=adj[koren2][koren1]=1; } } for (int node=0;node<N;node++) { if (parent[node]==node) {components[0].insert(node);components[1].insert(node);} } for (int node1=0;node1<N;node1++) { int koren1=get(node1); for (int node2=0;node2<N;node2++) { int koren2=get(node2);if (p[node1][node2]==0 and koren1==koren2) return 0; } } for (int node:components[0]) { if (components[1].find(node)==components[1].end()) continue; korenovi.push_back(node); for (int sled:components[0]) { if (node==sled) continue; if (p[node][sled]==2 and components[1].find(sled)==components[1].end()) return 0; else if (p[node][sled]==2) korenovi.push_back(sled); } if (korenovi.size()==2) return 0; for (int koren:korenovi) components[1].erase(koren); for (int poz=0;poz<korenovi.size()-1;poz++) { int node1=korenovi[poz],node2=korenovi[poz+1];adj[node1][node2]=adj[node2][node1]=1; if (siz[node1]<siz[node2]) swap(node1,node2); parent[node2]=node1;siz[node1]+=siz[node2]; } int node1=korenovi[0],node2=korenovi[korenovi.size()-1];adj[node1][node2]=adj[node2][node1]=1;korenovi.clear(); if (components[1].size()==0) break; } for (int node1=0;node1<N;node1++) { adj[node1][node1]=0; for (int node2=0;node2<N;node2++) { int koren1=get(node1),koren2=get(node2); if (p[node1][node2]==0 and koren1==koren2) return 0; } } build(adj);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...