Submission #302302

#TimeUsernameProblemLanguageResultExecution timeMemory
302302grtConnecting Supertrees (IOI20_supertrees)C++17
56 / 100
283 ms30456 KiB
#include <bits/stdc++.h> #define PB push_back #define ST first #define ND second #define _ ios_base::sync_with_stdio(0); cin.tie(0); //mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); using namespace std; using ll = long long; using pi = pair<int,int>; using vi = vector<int>; const int nax = 1000 + 10; int n; vi V1[nax], V2[nax]; bool done1[nax], done2[nax]; vi act = {}, cyc = {}; bool ont[nax]; vector<vi>g; vi tmp[nax]; void build(vector<vi> b); void dfs1(int x) { done1[x] = 1; act.PB(x); for(int nbh : V1[x]) if(!done1[nbh]) { dfs1(nbh); } } void dfs2(int x) { done2[x] = 1; act.PB(x); for(int nbh : V2[x]) if(ont[nbh] && !done2[nbh]) { dfs2(nbh); } } int construct(vector<vi>p) { n = (int)p.size(); g.resize(n); for(int i = 0; i < n; ++i) { g[i].resize(n); for(int j = 0; j < n; ++j) { if(p[i][j] == 3) { return 0; } if(p[i][j] == 1) { V1[i].PB(j); V1[j].PB(i); } else if(p[i][j] == 2) { V2[i].PB(j); V2[j].PB(i); } } } for(int i = 0; i < n; ++i) { if(!done1[i]) { act = {}; dfs1(i); ont[i] = 1; tmp[i] = act; for(int x : act) { for(int y : act) { if(p[x][y] != 1) return 0; } } cyc.PB(i); int a = i; for(int x : act) { if(x != a) { g[x][a] = g[a][x] = 1; } } } } for(int x : cyc) { if(!done2[x]) { act = {}; dfs2(x); if((int)act.size() ==1 ) continue; for(int x1 : act) { for(int y : act) { if(x1 != y) { for(int y1 : tmp[y]) { if(p[x1][y1] != 2) { return 0; } } } } } for(int j = 1; j < (int)act.size(); ++j) { g[act[j]][act[j - 1]] = g[act[j - 1]][act[j]] = 1; } g[act[0]][act.back()] = g[act.back()][act[0]] = 1; } } //~ for(int i = 0; i < n; ++i) { //~ cout << ont[i] << " "; //~ for(int j = 0; j < n; ++j) { //~ cout << g[i][j] << " "; //~ } //~ cout << "\n"; //~ } build(g); return 1; } //~ int main() { //~ cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 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...