| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 415103 | Kevin_Zhang_TW | Simurgh (IOI17_simurgh) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing
int qry(vector<int> r) { return count_common_roads(r); }
const int MAX_N = 505;
int id[MAX_N][MAX_N], state[MAX_N][MAX_N];
int dep[MAX_N], pa[MAX_N], n;
bool vis[MAX_N], on_tree[MAX_N][MAX_N];
vector<pair<int,int>> te, alle;
vector<int> tid;
void dfs(int x, int lst) {
pa[x] = lst;
dep[x] = dep[lst] + 1;
vis[x] = true;
for (int i = 0;i < n;++i) if (!vis[i] && id[x][i] != -1) {
dfs(i, x);
te.pb(i, x);
tid.pb(id[i][x]);
on_tree[i][x] = on_tree[x][i] = true;
}
}
pair<vector<int>, vector<int>> get_path(int a, int b) {
vector<int> l, r;
while (a != b) {
if (dep[a] > dep[b]) {
l.pb(a);
a = pa[a];
}
else {
r.pb(b);
b = pa[b];
}
}
return {l, r};
}
vector<int> operator - (vector<int> a, int v) { assert(count(AI(a) v); a.erase(find(AI(a), v)); return a; }
vector<int> operator + (vector<int> a, int v) { a.pb(v); return a; }
struct dsu {
vector<int> g, sz;
int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
bool M(int a, int b) {
a = F(a), b = F(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
return g[b] = a, sz[a] += sz[b], true;
}
dsu(int n) { g.resize(n+10), sz.resize(n+10, 1); iota(AI(g), 0); }
};
int get_cnt(vector<int> part) {
vector<int> r = part;
dsu D(n);
for (int id : part) {
auto [a, b] = alle[id];
D.M(a, b);
}
int sum = 0;
for (auto [a, b] : te)
if (D.M(a, b)) {
r.pb(id[a][b]);
sum += state[a][b];
}
assert(r.size() == n-1);
return qry(r) - sum;
}
void bs(vector<int> part, int sum) {
if (sum == 0) return;
if (part.size() == 1) {
auto [a, b] = alle[ part[0] ];
state[a][b] = state[b][a] = 1;
return;
}
int mid = part.size()/2;
vector<int> l, r;
for (int i = 0;i < part.size();++i)
(i<mid?l:r).pb(part[i]);
bs(l, get_cnt(l));
bs(r, get_cnt(r));
}
void solve(int h) {
vector<int> cur;
for (int i = 0;i < n;++i) if (id[h][i] != -1 && state[i][h] == -1)
cur.pb(id[h][i]);
if (cur.empty()) return;
bs(cur, get_cnt(cur));
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
int m = u.size();
::n = n;
for (int i = 0;i < n;++i) fill(id[i], id[i] + n, -1);
for (int i = 0;i < m;++i) {
int a = u[i], b = v[i];
alle.pb(a, b);
id[a][b] = id[b][a] = i;
state[a][b] = state[b][a] = -1;
}
dfs(0, 0);
int tsum = qry(tid);
for (int i = 0;i < m;++i) {
auto [a, b] = alle[i];
if (on_tree[a][b]) continue;
auto [l, r] = get_path(a, b);
int cnt = 0;
vector<int> not_sure, sure;
for (int u : l)
if (state[u][ pa[u] ] == -1)
not_sure.pb(id[u][pa[u]]);
else sure.pb(id[u][pa[u]]);
for (int u : r)
if (state[u][ pa[u] ] == -1)
not_sure.pb(id[u][pa[u]]);
else sure.pb(id[u][pa[u]]);
if (not_sure.empty()) continue;
vector<int> small, same, big;
for (int eid : not_sure) {
int qv = qry( (tid - eid) + id[a][b] );
if (qv > tsum) big.pb(eid);
if (qv == tsum) same.pb(eid);
if (qv < tsum) small.pb(eid);
}
for (int eid : big) {
auto [x, y] = alle[eid];
state[x][y] = state[y][x] = 0;
}
for (int eid : small) {
auto [x, y] = alle[eid];
state[x][y] = state[y][x] = 1;
}
int cur_v = -1;
if (small.size()) cur_v = 0;
if (big.size()) cur_v = 1;
if (cur_v == -1 && sure.size()) {
int qv = qry( (tid - sure[0]) + id[a][b] );
int x = v[ sure[0] ], y = u[ sure[0] ];
if (qv > tsum) cur_v = 0;
if (qv == tsum) cur_v = state[x][y];
if (qv < tsum) cur_v = 1;
}
if (cur_v == -1 && same.size() == l.size() + r.size())
cur_v = 0;
for (int eid : same) {
auto [x, y] = alle[eid];
state[y][x] = state[x][y] = cur_v;
}
state[b][a] = state[a][b] = cur_v;
}
for (auto [a, b] : te) {
if (state[a][b] == -1)
state[a][b] = state[b][a] = 1;
DE(a, b, state[a][b]);
}
for (int i = 0;i < n;++i) solve(i);
vector<int> res;
for (int i = 0;i < n;++i) for (int j = i+1;j < n;++j) {
if (id[i][j] == -1) continue;
if (state[i][j] == 1) res.pb(id[i][j]);
DE(i, j, state[i][j]);
}
return res;
}