Submission #759347

#TimeUsernameProblemLanguageResultExecution timeMemory
759347SharkyConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
220 ms23712 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1005; int N, fa[maxn], sz[maxn]; bool ok = true; int find(int u) { return (fa[u] == u) ? u : fa[u] = find(fa[u]); } bool merge(int u, int v) { u = find(u), v = find(v); if (u == v) return false; if (sz[v] > sz[u]) swap(u, v); fa[v] = u; sz[u] += sz[v]; return true; } bool vis[maxn]; vector<int> edits; void dfs(int u, vector<vector<int>>& ans, vector<vector<int>>& p) { vis[u] = true; edits.push_back(u); for (int i = 0; i < N; i++) { if (!vis[i] && p[u][i] == 1 && find(u) == find(i)) { ans[u][i] = ans[i][u] = 1; dfs(i, ans, p); } } } void process(vector<int> v, vector<vector<int>>& ans, vector<vector<int>>& p) { if ((int) v.size() == 1) return; // for (int i = 0; i < v.size(); i++) cout << v[i] << endl; int n = v.size(), cnt = 0; vector<int> cyc; vector<vector<int>> seen(N); vector<bool> in_cyc(N, 0); bool two = false; for (int i : v) { vector<bool> b(3, 0); for (int j = 0; j < N; j++) { if (i == j) continue; b[p[i][j]] = true; // cout << i << ' ' << j << ' ' << p[i][j] << '\n'; } for (int j = 0; j < N; j++) { if (p[i][j] == 1) merge(i, j); } if (b[2] && !b[1]) { cyc.push_back(i); // cout << "in cycle!" << ' ' << i << endl; in_cyc[i] = true; } two = (two | b[2]); } // cout << "alive\n"; for (int i = 0; i < n; i++) if (!in_cyc[v[i]]) { seen[find(v[i])].push_back(v[i]); // cout << "corresponding find: " << v[i] << ' ' << find(v[i]) << '\n'; } // cout << "alive\n"; for (int i = 0; i < N; i++) { if (seen[i].empty()) continue; dfs(seen[i].front(), ans, p); cyc.push_back(seen[i].front()); in_cyc[seen[i].front()] = true; seen[find(seen[i].front())].push_back(seen[i].front()); for (int j : edits) vis[j] = 0; } if (two && ((int) cyc.size() == 1 || (int) cyc.size() == 2)) { ok = false; return; } for (int i = 0; i < N; i++) if (!seen[i].empty()) cnt++; if (cnt > (int) cyc.size()) { ok = false; return; } for (int i = 0; i < cyc.size(); i++) { int nxt = (i + 1) % cyc.size(); ans[cyc[i]][cyc[nxt]] = ans[cyc[nxt]][cyc[i]] = 1; } } int construct(std::vector<std::vector<int>> p) { int n = p[0].size(); N = n; vector<vector<int>> ans(n, vector<int> (n, 0)); for (int i = 0; i < n; i++) { fa[i] = i, sz[i] = 1; for (int j = 0; j < n; j++) { if (p[i][j] >= 3) return 0; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j]) merge(i, j); } } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (!p[i][j] && find(i) == find(j)) return 0; } vector<vector<int>> g(n); for (int i = 0; i < n; i++) g[find(i)].push_back(i); for (int i = 0; i < n; i++) fa[i] = i, sz[i] = 1; for (int i = 0; i < n; i++) { if (!g[i].empty()) { process(g[i], ans, p); if (!ok) return 0; } } for (int i = 0; i < n; i++) ans[i][i] = 0; build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'void process(std::vector<int>, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
supertrees.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 0; i < cyc.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#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...