Submission #1202310

#TimeUsernameProblemLanguageResultExecution timeMemory
1202310onbertConnecting Supertrees (IOI20_supertrees)C++20
46 / 100
122 ms26184 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1005; int n; vector<vector<int>> G; bool vis[maxn]; bool inloop[maxn]; int belong[maxn]; vector<int> nodes; void dfs(int u) { vis[u] = true; nodes.push_back(u); for (int v=0;v<n;v++) if (G[u][v] && !vis[v]) dfs(v); } void dfs2(int u, int rt) { vis[u] = true, belong[u] = rt; for (int v=0;v<n;v++) if (G[u][v] == 1 && !vis[v]) dfs2(v, rt); } int construct(vector<vector<int>> p) { n = p.size(); G = p; vector<vector<int>> ans(n, vector<int>(n)); for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (G[i][j] == 3) return 0; for (int i=0;i<n;i++) belong[i] = -1; for (int i=0;i<n;i++) if (!vis[i]) { nodes.clear(); dfs(i); for (int u:nodes) vis[u] = false; vector<int> loop; for (int u:nodes) if (!vis[u]) { inloop[u] = true; loop.push_back(u); dfs2(u, u); } // cout << i << endl; // for (int u:nodes) cout << u << " "; cout << endl; // for (int u:loop) cout << u << " "; cout << endl; int sz = loop.size(); if (sz == 2) return false; if (sz > 2) { for (int j=0;j<sz;j++) ans[loop[j]][loop[(j+1)%sz]] = ans[loop[(j+1)%sz]][loop[j]] = 1; } for (int u:nodes) if (!inloop[u]) { bool done = false; for (int v:nodes) if (inloop[v] && G[u][v] == 1) { if (done) return 0; done = true; ans[u][v] = ans[v][u] = 1; belong[u] = v; } } for (int u:nodes) if (!inloop[u]) for (int v:nodes) if (!inloop[v]) { if (G[u][v] == 1 && belong[u] != belong[v]) return 0; } } 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...