Submission #977559

#TimeUsernameProblemLanguageResultExecution timeMemory
977559josanneo22Swapping Cities (APIO20_swap)C++17
100 / 100
312 ms43424 KiB
#include "swap.h" #include <vector> #include <bits/stdc++.h> using namespace std; const int nax = 300500, K = 22; int N, M; vector<pair<int, pair<int, int>>> edges; int fa[nax]; int child[nax][2]; int val[nax]; int dep[nax], sp[nax][K]; int st[nax], ed[nax]; bool chain[nax]; int find(int x) { if (x == fa[x]) return x; fa[x] = find(fa[x]); return fa[x]; } void dfs(int u, int f) { if (!u) return; // cout << "DFS : " << u << ' ' << f << '\n'; dep[u] = dep[f] + 1; sp[u][0] = f; for (int i = 1; i < K; i++) sp[u][i] = sp[sp[u][i - 1]][i - 1]; for (int t = 0; t < 2; t++) { int v = child[u][t]; dfs(v, u); } } int lca(int X, int Y) { if (dep[Y] >= dep[X]) swap(X, Y); for (int i = K - 1; i >= 0; i--) if (dep[sp[X][i]] >= dep[Y]) X = sp[X][i]; if (X == Y) return X; for (int i = K - 1; i >= 0; i--) if (sp[X][i] != sp[Y][i]) X = sp[X][i], Y = sp[Y][i]; return sp[X][0]; } int id; void init(int _N, int _M, std::vector<int> _U, std::vector<int> _V, std::vector<int> _W) { N = _N; M = _M; id = N; for (int i = 0 ; i < M; i++) edges.push_back(make_pair(_W[i], make_pair(_U[i] + 1, _V[i] + 1))); sort(edges.begin(), edges.end()); for (int i = 0; i < nax; i++) fa[i] = i; for (int i = 1; i <= N; i++) { chain[i] = true; st[i] = ed[i] = i; } for (int i = 0; i < edges.size(); i++) { int w = edges[i].first; int u = edges[i].second.first; int v = edges[i].second.second; int A = find(u), B = find(v); // cout << A << ' ' << B << '\n'; if (A == B) { if (chain[A]) { int g = ++id; fa[A] = g; val[g] = w; child[g][0] = A; } continue; } int g = ++id; fa[A] = g; fa[B] = g; val[g] = w; child[g][0] = A; child[g][1] = B; if (chain[A] && chain[B]) { // ...u, v... if (st[A] == v || ed[A] == v) swap(A, B); if (st[A] == u) swap(st[A], ed[A]); if (ed[B] == v) swap(st[B], ed[B]); if (ed[A] == u && st[B] == v) { chain[g] = true; st[g] = st[A]; ed[g] = ed[B]; } } } dfs(id, 0); // for (int i = 1; i <= 10; i++) cout << val[i] << ' '; // cout << '\n'; } int getMinimumFuelCapacity(int X, int Y) { X++; Y++; // cout << X << ' ' << Y << '\n'; int l = lca(X, Y); // cout << "lca : " << l << '\n'; if (!chain[l]) return val[l]; for (int i = K - 1; i >= 0; i--) if (sp[l][i] && chain[sp[l][i]]) l = sp[l][i]; if (l == id) return -1; return val[sp[l][0]]; } /* 要么是deg >= 3, 要么是cycle 考虑什么时候不能:链 我们可以直接维持kruskal重构树, 让chain[i] = true/false u, v -> new node 然后new node点权 = w 那么答案就是 在lca上倍增直到chain[i] = true为此 然后 ans = cal[fa[lca]] 判断chain[i] 可以用看u -> v是不是两个corner */

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for (int i = 0; i < edges.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
#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...