Submission #1214797

#TimeUsernameProblemLanguageResultExecution timeMemory
1214797Math4Life2020Connecting Supertrees (IOI20_supertrees)C++20
0 / 100
0 ms328 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; using ll = int; using pii = pair<ll,ll>; int construct(vector<vector<int>> p) { ll N = p.size(); vector<vector<int>> cstr(N,vector<ll>(N,0)); //construction for (ll i=0;i<N;i++) { for (ll j=0;j<N;j++) { if (p[i][j]==3) { return 0; } } } vector<bool> found(N,false); vector<bool> found2(N,false); for (int i=0;i<N;i++) { if (!found[i]) { vector<int> vin,vout; for (int j=0;j<N;j++) { if (p[i][j]!=0) { vin.push_back(j); found[j]=1; } else { vout.push_back(j); } } for (int a: vin) { for (int b: vin) { if (p[a][b]==0) { return 0; } } } for (int a: vin) { for (int b: vout) { if (p[a][b]!=0) { return 0; } } } vector<vector<int>> vclq; //cliques for (int x: vin) { if (!found2[x]) { vector<int> clqt; for (int y: vin) { if (p[x][y]==1) { if (found2[y]) { return 0; } found2[y]=1; clqt.push_back(y); } } vclq.push_back(clqt); } } for (auto v0: vclq) { ll m = v0.size(); for (ll i=1;i<m;i++) { cstr[v0[0]][v0[i]]=1; cstr[v0[i]][v0[0]]=1; } for (ll a: v0) { for (ll b: v0) { if (p[a][b]!=1) { return 0; } } } } ll sz = vclq.size(); for (ll i=0;i<sz;i++) { cstr[vclq[i][0]][vclq[(i+1)%sz][0]]=1; cstr[vclq[(i+1)%sz][0]][vclq[i][0]]=1; } for (ll i=0;i<sz;i++) { for (ll j=(i+1);j<sz;j++) { for (ll a: vclq[i]) { for (ll b: vclq[j]) { if (p[a][b]!=2) { //cout << "a,b="<<a<<","<<b<<"\n"; return 0; } } } } } } } build(cstr); 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...