Submission #1211142

#TimeUsernameProblemLanguageResultExecution timeMemory
1211142onbertSimurgh (IOI17_simurgh)C++17
19 / 100
795 ms6332 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; const int maxn = 505; int n; int id[maxn][maxn]; vector<int> adj[maxn]; bool a[maxn][maxn]; int gold[maxn][maxn], state[maxn]; int fa[maxn]; int goldcnt; void edge(int u, int v, bool x) { a[min(u, v)][max(u, v)] = x; } int qry() { vector<int> ask; int ret = 0; for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) if (a[i][j]) { ask.push_back(id[i][j]); ret -= (gold[i][j] == 1); } // for (int i:ask) cout << i << " "; cout << endl; return ret + count_common_roads(ask); } vector<int> nodes; bool vis[maxn]; void dfs0(int u) { vis[u] = true, nodes.push_back(u); for (int v:adj[u]) if (!vis[v] && state[v] <= 0) { edge(u, v, 1); dfs0(v); } } void dfs1(int u) { vis[u] = true; for (int v:adj[u]) if (!vis[v] && state[v] <= 0) { edge(u, v, 1); dfs1(v); } } void connect() { for (int i=0;i<n;i++) if (state[i] == 1) dfs1(i); } void dfs2(int u) { vis[u] = true; for (int v:adj[u]) if (!vis[v] && !(state[v] == 0 && state[u] <= 1)) { edge(u, v, 1); // cout << u << " " << v << endl; fa[v] = u; dfs2(v); } } void addnode(int u) { goldcnt++; state[u] = 2; // cout << u << endl; for (int i=0;i<n;i++) vis[i] = (state[i] == 2); for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = (gold[i][j] == 1); for (int i=0;i<n;i++) if (state[i] == 2 && i != u) dfs2(i); dfs2(u); vector<int> cand; for (int v:adj[u]) if (state[v] == 0) cand.push_back(v); // for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl; // cout << init << endl; int init = qry(); for (int v:cand) { edge(u, v, 1); edge(v, fa[v], 0); } int val = qry(); for (int v:cand) { edge(u, v, 0); edge(v, fa[v], 1); } // cout << endl; // for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl; // cout << val << endl; vector<int> add; for (int i=init + 1;i<=val;i++) { int l = 0, r = cand.size()-1; while (l < r) { int mid = (l+r)/2; for (int j=0;j<=mid;j++) { int v = cand[j]; edge(u, v, 1); edge(v, fa[v], 0); } int val = qry(); for (int j=0;j<=mid;j++) { int v = cand[j]; edge(u, v, 0); edge(v, fa[v], 1); } if (val >= i) r = mid; else l = mid+1; } int v = cand[l]; state[v] = 1; add.push_back(v); } for (int v:add) { fa[v] = u; gold[min(u, v)][max(u, v)] = 1; addnode(v); } } vector<int> find_roads(int N, vector<int> U, vector<int> V) { n = N; for (int i=0;i<n;i++) for (int j=0;j<n;j++) id[i][j] = -1, a[i][j] = 0, gold[i][j] = -1; for (int i=0;i<U.size();i++) { id[min(U[i], V[i])][max(U[i], V[i])] = i; adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); } for (int i=0;i<n;i++) state[i] = -1, fa[i] = -1; state[0] = 2; goldcnt = 1; while (goldcnt < n) { // cout << "start " << goldcnt << endl; for (int i=0;i<n;i++) vis[i] = (state[i] == 2); for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = (gold[i][j] == 1); for (int i=0;i<n;i++) if (state[i] <= 0) { nodes.clear(); dfs0(i); break; } // cout << "edges\n"; // for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl; // cout << "nodes\n"; // for (int i:nodes) cout << i << " "; cout << endl; connect(); vector<pair<int,int>> vec; int mx = 0; for (int u:nodes) if (state[u] == -1) { vector<int> cand; for (int v:adj[u]) if (state[v] == 2) cand.push_back(v); if (!cand.size()) continue; sort(cand.begin(), cand.end()); for (int v:cand) { edge(u, v, 1); if (v != cand[0]) edge(v, fa[v], 0); } int val = qry(); vec.push_back({u, val}); mx = max(val, mx); for (int v:cand) { edge(u, v, 0); if (v != cand[0]) edge(v, fa[v], 1); } } vector<pair<int,int>> add; for (auto [u, val]:vec) { vector<int> cand; for (int v:adj[u]) if (state[v] == 2) cand.push_back(v); sort(cand.begin(), cand.end()); if (val != mx) { state[u] = 0; fa[u] = cand[0]; } else { int l = 0, r = cand.size() - 1; while (l < r) { int mid = (l+r)/2; for (int i=0;i<=mid;i++) { int v = cand[i]; edge(u, v, 1); if (v != cand[0]) edge(v, fa[v], 0); } int val = qry(); for (int i=0;i<=mid;i++) { int v = cand[i]; edge(u, v, 0); if (v != cand[0]) edge(v, fa[v], 1); } if (val == mx) r = mid; else l = mid+1; } int v = cand[l]; // cout << "test " << u << " " << v << endl; // for (int j:cand) cout << j << " "; cout << endl; state[u] = 1; add.push_back({u, v}); } } for (auto [u, v]:add) { fa[u] = v; gold[min(u, v)][max(u, v)] = 1; addnode(u); // cout << u << " " << v << endl; } // cout << "test " << goldcnt << endl;; // cout << goldcnt << endl; } vector<int> ans; for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (gold[i][j] == 1) { ans.push_back(id[i][j]); } return ans; }
#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...