Submission #1211112

#TimeUsernameProblemLanguageResultExecution timeMemory
1211112onbertSimurgh (IOI17_simurgh)C++17
19 / 100
3094 ms6328 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] <= 0)) { edge(u, v, 1); fa[v] = u; dfs2(v); } } void addnode(int u) { goldcnt++; for (int i=0;i<n;i++) vis[i] = (state[i] == 1); 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] == 1 && i != u) dfs2(i); vector<int> cand; for (int v:adj[u]) if (!state[v]) cand.push_back(v); int init = qry(); // 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; 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); } if (val == init) return; // 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]; add.push_back(v); } for (int v:add) { fa[v] = u; state[v] = 1; gold[min(u, v)][max(u, v)] = 1; } for (int v:add) 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] = 1; goldcnt = 1; while (goldcnt < n) { for (int i=0;i<n;i++) vis[i] = (state[i] == 1); 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; } connect(); // 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; 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] == 1) 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] == 1) 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+1)/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) l = mid; else r = mid-1; } int v = cand[l]; add.push_back({u, v}); } } for (auto [u, v]:add) { state[u] = 1; fa[u] = v; gold[min(u, v)][max(u, v)] = 1; // cout << u << " " << v << endl; } for (auto [u, v]:add) addnode(u); } 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]); // cout << i << " " << j << " " << id[i][j] << endl; } 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...