Submission #961872

#TimeUsernameProblemLanguageResultExecution timeMemory
961872Nhoksocqt1Swapping Cities (APIO20_swap)C++17
100 / 100
1700 ms145880 KiB
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define sz(x) int((x).size()) #define fi first #define se second typedef long long ll; typedef pair<int, int> ii; template<class X, class Y> inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);} template<class X, class Y> inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int Random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } const int MAXN = 100005; class DisjointSet { private: vector<int> lab, id; public: DisjointSet(int _n = 0) { lab.assign(_n + 7, -1); id.resize(_n + 7); for (int i = 0; i <= _n; ++i) id[i] = i; } int find(int u) { return (lab[u] < 0) ? u : (lab[u] = find(lab[u])); } void updateID(int u, int newID) { id[find(u)] = newID; } bool join(int u, int v) { u = find(u), v = find(v); if(u == v) return (false); if(lab[u] > lab[v]) swap(u, v); lab[u] += lab[v]; lab[v] = u; return (true); } int getSize(int u) { return -lab[find(u)]; } int getID(int u) { return id[find(u)]; } } dsu; struct Edge { int u, v, w; } edge[2 * MAXN]; struct SegNode { int cnt, L, R; } seg[50 * MAXN]; vector<int> idw; vector<ii> adj[MAXN], adjp[3 * MAXN]; int depth2[3 * MAXN], nodew[3 * MAXN], fstOk[3 * MAXN], cntNode[3 * MAXN], cntEdge[3 * MAXN], P2[3 * MAXN][19]; int version[MAXN], tIn[MAXN], tOut[MAXN], tour[MAXN], depth[MAXN], P[MAXN][17], Pw[MAXN][17]; int deg[MAXN], pa[MAXN], cntLeaf[MAXN], tmp[MAXN], cntChild[MAXN], maxw, nTree, nNode, numNode, numEdge; bool dp[1003][1003], dx[MAXN], check_sub1, check_sub2; int cntTime(0); void preDfs(int u) { tIn[u] = ++cntTime; tour[cntTime] = u; ++tmp[tIn[u]]; for (int it = 0; it < sz(adj[u]); ++it) { int v(adj[u][it].fi), id(adj[u][it].se); if(v != P[u][0]) { depth[v] = depth[u] + 1; P[v][0] = u; Pw[v][0] = id; preDfs(v); --tmp[tIn[u]]; } } tOut[u] = cntTime; } int lca(int u, int v) { if(depth[u] < depth[v]) swap(u, v); for (int i1 = depth[u] - depth[v]; i1 > 0; i1 ^= i1 & -i1) { int i = __builtin_ctz(i1); u = P[u][i]; } if(u == v) return u; for (int i = 31 - __builtin_clz(depth[u]); i >= 0; --i) { if(P[u][i] != P[v][i]) u = P[u][i], v = P[v][i]; } return P[u][0]; } int build(int l, int r, int tmp[]) { if(l == r) { seg[++nTree].cnt = tmp[l]; return nTree; } int cur(++nTree), mid = (l + r) >> 1; seg[cur].L = build(l, mid, tmp); seg[cur].R = build(mid + 1, r, tmp); seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt; return cur; } int update(int oldID, int l, int r, int pos, int val) { if(l == r) { seg[++nTree] = seg[oldID]; seg[nTree].cnt += val; return nTree; } int cur(++nTree), mid = (l + r) >> 1; seg[cur] = seg[oldID]; if(pos <= mid) { seg[cur].L = update(seg[oldID].L, l, mid, pos, val); } else { seg[cur].R = update(seg[oldID].R, mid + 1, r, pos, val); } seg[cur].cnt = seg[seg[cur].L].cnt + seg[seg[cur].R].cnt; return cur; } int query(int id, int l, int r, int u, int v) { if(u <= l && r <= v) return seg[id].cnt; int mid = (l + r) >> 1, res(0); if(mid >= u) res += query(seg[id].L, l, mid, u, v); if(mid + 1 <= v) res += query(seg[id].R, mid + 1, r, u, v); return res; } void preDfs2(int u) { cntEdge[u] = (u >= numNode); cntNode[u] = (u < numNode); for (int it = 0; it < sz(adjp[u]); ++it) { int v(adjp[u][it].fi), w(adjp[u][it].se); nodew[u] = w, P2[v][0] = u; depth2[v] = depth2[u] + 1; preDfs2(v); cntNode[u] += cntNode[v]; cntEdge[u] += cntEdge[v]; } } void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W) { numNode = _N, numEdge = _M; for (int i = 0; i < numEdge; ++i) { edge[i] = {_U[i], _V[i], _W[i]}; maxw = max(maxw, edge[i].w); ++deg[edge[i].u], ++deg[edge[i].v]; } check_sub1 = 1; for (int i = 0; i < numNode; ++i) check_sub1 &= (deg[i] <= 2); sort(edge, edge + numEdge, [](const Edge &a, const Edge &b) { return (a.w < b.w); }); dsu = DisjointSet(numNode); nNode = numNode; for (int i = 0; i < numNode; ++i) cntNode[i] = 1; int cnt(0); for (int i = 0; i < numEdge; ++i) { int u(edge[i].u), v(edge[i].v); adjp[nNode].push_back(ii(dsu.getID(u), i)); if(dsu.find(u) != dsu.find(v)) { idw.push_back(edge[i].w); adj[u].push_back(ii(v, cnt)); adj[v].push_back(ii(u, cnt)); adjp[nNode].push_back(ii(dsu.getID(v), i)); dsu.join(u, v); ++cnt; } dsu.updateID(u, nNode); ++nNode; } P[0][0] = -1, depth[0] = 1; preDfs(0); for (int j = 1; (1 << j) <= numNode; ++j) { for (int i = 0; i < numNode; ++i) { if(P[i][j - 1] == -1) { P[i][j] = -1; } else { P[i][j] = P[P[i][j - 1]][j - 1]; Pw[i][j] = max(Pw[i][j - 1], Pw[P[i][j - 1]][j - 1]); } } } P2[nNode - 1][0] = -1, depth2[nNode - 1] = 1; preDfs2(nNode - 1); fstOk[nNode - 1] = (cntEdge[nNode - 1] >= cntEdge[nNode - 1]) ? nNode - 1 : -1; for (int i = nNode - 2; i >= 0; --i) fstOk[i] = (cntEdge[i] >= cntNode[i]) ? i : fstOk[P2[i][0]]; for (int j = 1; (1 << j) <= nNode; ++j) { for (int i = 0; i < nNode; ++i) { if(P2[i][j - 1] != -1) { P2[i][j] = P2[P2[i][j - 1]][j - 1]; } else { P2[i][j] = -1; } } } cnt = 0; dsu = DisjointSet(numNode); version[0] = build(1, numNode, tmp); for (int i = 0; i < numEdge; ++i) { int u(edge[i].u), v(edge[i].v); if(dsu.find(u) != dsu.find(v)) { if(P[u][0] == v) swap(u, v); ++cnt; int qr = query(version[cnt - 1], 1, numNode, tIn[v], tOut[v]) - (++cntChild[u] == 2); version[cnt] = update(version[cnt - 1], 1, numNode, tIn[u], qr); if(++cntChild[v] == 2) { version[cnt] = update(version[cnt], 1, numNode, tIn[v], -1); --qr; } int w(u); for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) { if(P[w][i] != -1 && dsu.find(P[w][i]) == dsu.find(u)) w = P[w][i]; } w = P[w][0]; if(w != -1) version[cnt] = update(version[cnt], 1, numNode, tIn[w], -qr); dsu.join(u, v); } } } ii dfs(int u) { dx[u] = 1; cntLeaf[u] = 0; ii res = {sz(adj[u]), 1}; for (int it = 0; it < sz(adj[u]); ++it) { int v(adj[u][it].fi); if(!dx[v]) { pa[v] = u; ii tmp = dfs(v); res = {res.fi + tmp.fi, res.se + tmp.se}; cntLeaf[u] += cntLeaf[v]; } } if(cntLeaf[u] == 0) cntLeaf[u] = 1; return res; } int brute(int x, int y) { int l(0), r(numEdge - 1), ans(-1); while(l <= r) { int mid = (l + r) >> 1; for (int i = 0; i < numNode; ++i) { adj[i].clear(); dx[i] = 0; } for (int i = 0; i <= mid; ++i) { int u(edge[i].u), v(edge[i].v); adj[u].push_back(ii(v, 0)); adj[v].push_back(ii(u, 0)); } pa[x] = -1; ii res = dfs(x); bool check(0); if(dx[y]) { int u(y); while(pa[u] != x) u = pa[u]; check = (res.fi / 2 >= res.se || cntLeaf[y] > 1 || cntLeaf[x] - cntLeaf[u] > 1 || cntLeaf[u] - cntLeaf[y] > 0); } if(check) { ans = edge[mid].w; r = mid - 1; } else { l = mid + 1; } } return ans; } int sub5(int x, int y) { int l(0), r(numNode - 1), ans(-1); int par = lca(x, y); int tmp(x); for (int i1 = depth[x] - depth[par]; i1 > 0; i1 ^= i1 & -i1) { int i = __builtin_ctz(i1); l = max(l, Pw[tmp][i]); tmp = P[tmp][i]; } tmp = y; for (int i1 = depth[y] - depth[par]; i1 > 0; i1 ^= i1 & -i1) { int i = __builtin_ctz(i1); l = max(l, Pw[tmp][i]); tmp = P[tmp][i]; } if(par == y) swap(x, y); int c(-1); if(par == x) { c = y; for (int i1 = depth[y] - depth[x] - 1; i1 > 0; i1 ^= i1 & -i1) { int i = __builtin_ctz(i1); c = P[c][i]; } } while(l <= r) { int mid = (l + r) >> 1; bool check(0); if(par == x) { int w(x); for (int i = 31 - __builtin_clz(depth[w]); i >= 0; --i) { if(P[w][i] != -1 && Pw[w][i] <= mid) w = P[w][i]; } int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]); if(cntLeafy <= 1) { int cntLeafc = query(version[mid + 1], 1, numNode, tIn[c], tOut[c]); int cntLeafx = query(version[mid + 1], 1, numNode, tIn[w], tOut[w]) - cntLeafc; if(cntLeafx <= 1) { int cntLeafInPath = cntLeafc - cntLeafy; check = (cntLeafInPath > 0); } else { check = 1; } } else { check = 1; } } else { if(par > 0 && Pw[par][0] <= mid) { check = 1; } else { int cntLeafx = query(version[mid + 1], 1, numNode, tIn[x], tOut[x]); if(cntLeafx <= 1) { int cntLeafy = query(version[mid + 1], 1, numNode, tIn[y], tOut[y]); if(cntLeafy <= 1) { int cntLeafInPath = query(version[mid + 1], 1, numNode, tIn[par], tOut[par]) - cntLeafx - cntLeafy; check = (cntLeafInPath > 0); } else { check = 1; } } else { check = 1; } } } if(check) { ans = idw[mid]; r = mid - 1; } else { l = mid + 1; } } return ans; } int lca2(int u, int v) { if(depth2[u] < depth2[v]) swap(u, v); for (int i1 = depth2[u] - depth2[v]; i1 > 0; i1 ^= i1 & -i1) { int i = __builtin_ctz(i1); u = P2[u][i]; } if(u == v) return u; for (int i = 31 - __builtin_clz(depth2[u]); i >= 0; --i) { if(P2[u][i] != P2[v][i]) u = P2[u][i], v = P2[v][i]; } return P2[u][0]; } int magicFunc(int x, int y) { int ansTree = sub5(x, y); int p = fstOk[lca2(x, y)]; int ans = (p < 0) ? -1 : edge[nodew[p]].w; if(ansTree < 0 || ans < 0) { ans = (ans < 0) ? ansTree : ans; } else { ans = min(ans, ansTree); } return ans; } int getMinimumFuelCapacity(int x, int y) { /*cout << magicFunc(x, y) << ' ' << brute(x, y) << '\n'; if(magicFunc(x, y) != brute(x, y)) exit(1);*/ if(check_sub1) return (numNode == numEdge) ? maxw : -1; if(numEdge == numNode - 1) return sub5(x, y); return magicFunc(x, y); } #ifdef Nhoksocqt1 int main(void) { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define TASK "swap" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } vector<int> _U, _V, _W; int _N, _M, _Q; cin >> _N >> _M >> _Q; //_N = Random(5e1, 1e2), _M = Random(_N - 1, 2 * _N), _Q = Random(5e4, 2e5); cout << _N << ' ' << _M << ' ' << _Q << '\n'; _U.resize(_M), _V.resize(_M), _W.resize(_M); for (int i = 0; i < _M; ++i) { cin >> _U[i] >> _V[i] >> _W[i]; //if(i < _N - 1) _U[i] = Random(max(0, i - 10), i), _V[i] = i + 1; if(i >= _N - 1) _U[i] = Random(0, _N - 2), _V[i] = Random(_U[i] + 1, _N - 1); _W[i] = Random(1, 1e5); cout << _U[i] << ' ' << _V[i] << ' ' << _W[i] << '\n'; } init(_N, _M, _U, _V, _W); for (int t = 0; t < _Q; ++t) { int _X, _Y; cin >> _X >> _Y; //_X = Random(0, _N - 2), _Y = Random(_X + 1, _N - 1); cout << "MINIMUM FUEL CAPACITY " << _X << " TO " << _Y << ": " << getMinimumFuelCapacity(_X, _Y) << '\n'; if(t % 100 == 0) cerr << "RUNNING ON QUERY " << t << '\n'; } return 0; } #endif // Nhoksocqt1

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:241:44: warning: self-comparison always evaluates to true [-Wtautological-compare]
  241 |     fstOk[nNode - 1] = (cntEdge[nNode - 1] >= cntEdge[nNode - 1]) ? nNode - 1 : -1;
      |                         ~~~~~~~~~~~~~~~~~~ ^~ ~~~~~~~~~~~~~~~~~~
#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...