Submission #331193

#TimeUsernameProblemLanguageResultExecution timeMemory
331193arujbansalSwapping Cities (APIO20_swap)C++17
6 / 100
375 ms49224 KiB
#include "swap.h" #include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) #define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout) #define rand_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int) (x).size() #define lc(i) 2*i #define rc(i) 2*i+1 //#define int long long using namespace std; using ll = long long; using ii = pair<int, int>; using vii = vector<ii>; using vi = vector<int>; using vvi = vector<vi>; using vb = vector<bool>; using vvb = vector<vb>; //rand_init; const int MAXN = 5e5 + 5, MAXM = 4e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5; struct Edge { int u, v, w; Edge(int u, int v, int w) : u(u), v(v), w(w) {} bool operator<(const Edge &other) { return w < other.w; } }; int n, m, fakeNode, timer = 0; const int MAXK = 20; vector<Edge> edges; vi g[MAXN]; int par[MAXN], cost[MAXN], deg[MAXN], binlift[MAXN][MAXK], minCost[MAXN], tin[MAXN], tout[MAXN]; bool valid[MAXN]; void addEdge(int u, int w) { g[u].pb(fakeNode); g[fakeNode].pb(u); cost[fakeNode] = w; valid[fakeNode] |= valid[u]; } int get(int x) { return (par[x] == x ? x : par[x] = get(par[x])); } void unite(int x, int y, int w) { // cout << "Edge unite: " << x << " " << y << " " << w << "\n"; int u = get(x), v = get(y); deg[x]++; deg[y]++; valid[u] |= (deg[x] >= 3); valid[v] |= (deg[y] >= 3); u = get(u), v = get(v); if (u == v) { addEdge(u, w); par[u] = fakeNode; valid[fakeNode] = true; fakeNode++; return; } addEdge(u, w); addEdge(v, w); par[u] = fakeNode; par[v] = fakeNode; fakeNode++; } void dfs(int u = fakeNode, int p = -1) { if (valid[u]) minCost[u] = cost[u]; if (p != -1) { binlift[u][0] = p; minCost[u] = min(minCost[u], minCost[p]); } tin[u] = timer++; for (int j = 1; j < MAXK; j++) { if (binlift[u][j - 1] < 0) continue; binlift[u][j] = binlift[binlift[u][j - 1]][j - 1]; } for (const auto &v : g[u]) if (v != p) dfs(v, u); tout[u] = timer - 1; } bool isAnc(int x, int y) { return (tin[x] <= tin[y] && tout[x] >= tout[y]); } int queryLCA(int u, int v) { if (isAnc(u, v)) return u; if (isAnc(v, u)) return v; for (int j = MAXK - 1; j >= 0; j--) if (binlift[u][j] > -1 && !isAnc(binlift[u][j], v)) u = binlift[u][j]; return binlift[u][0]; } void init(int N, int M, vi U, vi V, vi W) { n = N, m = M; for (int i = 0; i < m; i++) edges.eb(U[i], V[i], W[i]); sort(all(edges)); // Initialise UFDS stuff iota(par, par + 2 * n, 0); fakeNode = n; for (const auto &[u, v, w] : edges) unite(u, v, w); fakeNode--; for (int i = 0; i <= fakeNode; i++) minCost[i] = INF; for (int i = 0; i <= fakeNode; i++) { for (int j = 0; j < MAXK; j++) { binlift[i][j] = -1; } } dfs(); } int getMinimumFuelCapacity(int X, int Y) { int lca = queryLCA(X, Y); // cout << "LCA: " << lca << "\n"; return (minCost[lca] < INF ? minCost[lca] : -1); } //void solve() { // int a, b; // cin >> a >> b; // vi u(b), v(b), wt(b); // // for (int i = 0; i < b; i++) // cin >> u[i] >> v[i] >> wt[i]; // // init(a, b, u, v, wt); // // int q; // cin >> q; // while (q--) { // int x, y; // cin >> x >> y; // cout << getMinimumFuelCapacity(x, y) << "\n"; // } //} // //signed main() { // FAST_IO; //#ifdef arujbansal_local // setIO("input.txt", "output.txt"); //#endif // // int tc = 1; //// cin >> tc; // while (tc--) solve(); //}
#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...