Submission #70710

#TimeUsernameProblemLanguageResultExecution timeMemory
70710aquablitz11Simurgh (IOI17_simurgh)C++14
0 / 100
1499 ms1049600 KiB
#include <bits/stdc++.h> #include "simurgh.h" using namespace std; using pii = pair<int, int>; #define F first #define S second const int N = 510; const int M = N*(N-1)/2; const int LIM = 30000; int n, m; vector<int> U, V; // edge list vector<pii> G[N]; // adj list vector<int> T; // tree edges vector<pii> GT[N]; // tree adj list bool is_tree[M]; int ans[M]; // answer to each edge (-1 = unknown) int defcnt; // answer for the default spanning tree int tick; pii disc[N], low[N]; void dfs(int u, int p) { disc[u] = low[u] = pii(++tick, -1); for (auto v : G[u]) { if (!disc[v.F].F) { // push edge to tree is_tree[v.S] = true; T.push_back(v.S); GT[u].emplace_back(v.F, v.S); GT[v.F].emplace_back(u, v.S); // tarjan's algorithm dfs(v.F, u); low[u] = min(low[u], low[v.F]); if (low[v.F].F > disc[u].F) ans[v.S] = 1; } else { low[u] = min(low[u], pii(disc[v.F].F, v.S)); } } } vector<int> find_path(int u, int e, int t) { if (u == t) { vector<int> ret; ret.push_back(e); return ret; } for (auto v : GT[u]) if (v.S != e) { vector<int> ret = find_path(v.F, v.S, t); if (!ret.empty()) { if (e != -1) ret.push_back(e); return ret; } } return vector<int>(); } int get_changes(int rem, int add) { vector<int> q(T); q.erase(find(q.begin(), q.end(), rem)); q.push_back(add); return count_common_roads(q) - defcnt; } void query_cycle(int ce) { if (ans[ce] != -1) return; int s = U[ce], t = V[ce]; vector<int> path = find_path(s, -1, t); // find edge in path that we already know answer to int fnd = -1; for (auto e : path) { if (ans[e] != -1) { fnd = e; break; } } if (fnd != -1) { // case where we can quickly determine ce's value ans[ce] = ans[fnd] + get_changes(fnd, ce); for (auto e : path) { // update other edge in path we don't know if (ans[e] == -1) ans[e] = ans[ce] - get_changes(e, ce); } } else { // don't know, so query everything in the cycle for (auto e : path) { int d = get_changes(e, ce); if (d == 1) ans[ce] = 1, ans[e] = 0; else if (d == -1) ans[ce] = 0, ans[e] = 1; } if (ans[ce] == -1) ans[ce] = 0; for (auto e : path) { if (ans[e] == -1) ans[e] = ans[ce]; } } } int par[N]; int root(int u) { if (par[u] == u) return u; return par[u] = root(par[u]); } bool merge(int u, int v) { u = root(u), v = root(v); if (u == v) return false; par[u] = v; return true; } int query_adj(vector<int> &adj) { if (adj.empty()) return 0; iota(par, par+n, 0); vector<int> q; for (auto e : adj) { merge(U[e], V[e]); q.push_back(e); } int cnt = 0; for (auto e : T) { if (merge(U[e], V[e])) { cnt += ans[e]; q.push_back(e); } } int ret = count_common_roads(q); return ret-cnt; } void solve(vector<int> &adj, int cnt = -1) { if (cnt == -1) cnt = query_adj(adj); if (cnt == 0) { for (auto e : adj) ans[e] = 0; return; } if (cnt == adj.size()) { for (auto e : adj) ans[e] = 1; return; } int mid = adj.size()/2; vector<int> L(adj.begin(), adj.begin()+mid); vector<int> R(adj.begin()+mid, adj.end()); int lcnt = query_adj(L); solve(L, lcnt); solve(R, cnt-lcnt); } vector<int> find_roads(int _n, vector<int> _U, vector<int> _V) { // create adj list n = _n; U = _U, V = _V; m = U.size(); for (int i = 0; i < m; ++i) { int u = U[i], v = V[i]; G[u].emplace_back(v, i); G[v].emplace_back(u, i); } // build dfs tree and find answer for the tree fill(ans, ans+m, -1); dfs(1, -1); defcnt = count_common_roads(T); for (int i = 0; i < n; ++i) { if (low[i].S != -1) query_cycle(low[i].S); } // find answer for each node for (int u = 0; u < n; ++u) { vector<int> adj; for (auto v : G[u]) { if (ans[v.S] == -1) adj.push_back(v.S); } solve(adj); } // return answer vector<int> ret; for (int i = 0; i < m; ++i) { if (ans[i]) ret.push_back(i); } return ret; }

Compilation message (stderr)

simurgh.cpp: In function 'void solve(std::vector<int>&, int)':
simurgh.cpp:150:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cnt == adj.size()) {
         ~~~~^~~~~~~~~~~~~
#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...