Submission #1109715

#TimeUsernameProblemLanguageResultExecution timeMemory
1109715Mike_VuSwapping Cities (APIO20_swap)C++14
13 / 100
258 ms61756 KiB
#ifndef mikevui // #include "task.h" #endif // mikevui #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double dou; #define pii pair<int, int> #define fi first #define se second #define pb push_back #define MASK(x) (1LL<<(x)) #define BITj(x, j) (((x)>>(j))&1) template<typename T> bool maximize(T &x, const T &y) { if (x < y) {x = y; return 1;} return 0; } template<typename T> bool minimize(T &x, const T &y) { if (x > y) {x = y; return 1;} return 0; } struct edge{ int u, v, w; edge(int _u, int _v, int _w) { u = _u; v = _v; w = _w; } }; const int maxn = 3e5+5, lg = 19; int n, m, trsz; vector<edge> edges; bool can[maxn]; int ans[maxn]; vector<int> adj[maxn]; int par[maxn][lg+1], h[maxn]; bool hadcan[maxn][lg+1]; namespace dsu{ vector<int> dsu, deg, sumdeg; void init() { trsz = n; memset(can, 0, sizeof(can)); dsu.assign(trsz+1, 0); deg.assign(trsz+1, 0); sumdeg.assign(trsz+1, 1); for (int i = 1; i <= n; i++) { dsu[i] = i; } } int f(int u) { if (u == dsu[u]) return u; return dsu[u] = f(dsu[u]); } void addedge(int u, int v) { int ru = f(u), rv = f(v); ++trsz; dsu.pb(trsz); dsu[ru] = dsu[rv] = trsz; adj[trsz].pb(ru); if (ru != rv) adj[trsz].pb(rv); ++deg[u]; ++deg[v]; //check cycle sumdeg.pb(sumdeg[ru]); if (ru != rv) sumdeg[trsz] += sumdeg[rv]; if (deg[u] == 2)--sumdeg[trsz]; if (deg[v] == 2)--sumdeg[trsz]; // cout << u << ' ' << v << ' ' << trsz << "\n" << deg[u] << ' ' << deg[v] << ' ' << sumdeg[ru] << ' ' << sumdeg[rv] << ' ' << sumdeg[trsz] << "\n"; can[trsz] = (max(deg[u], deg[v])>2 || sumdeg[trsz] == 0); } } void dfs(int u) { //setup binlift for (int j = 1; j <= lg; j++) { par[u][j] = par[par[u][j-1]][j-1]; hadcan[u][j] = hadcan[u][j-1]|hadcan[par[u][j-1]][j-1]; } //dfs for (int v : adj[u]) { par[v][0] = u; hadcan[v][0] = can[u]; h[v] = h[u]+1; dfs(v); } } int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); if (h[u] > h[v]) { int k = h[u]-h[v]; for (int j = lg; j >= 0; j--) { if (BITj(k, j)) { u = par[u][j]; } } } if (u == v) return u; for (int j = lg; j >= 0; j--) { while (h[u] > MASK(j) && par[u][j] != par[v][j]) { u = par[u][j]; v = par[v][j]; } } return par[u][0]; } int findnearest(int u){ for (int j = lg; j >= 0; j--) { while (h[u] > MASK(j) && !hadcan[u][j]) { u = par[u][j]; } } return par[u][0]; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { //transform to normal use n = N; m = M; for (int i = 0; i < m; i++) { int u = U[i]+1, v = V[i]+1, w = W[i]; edges.pb(edge(u, v, w)); } //build dsu tree sort(edges.begin(), edges.end(), [&](edge a, edge b){return a.w<b.w;}); dsu::init(); for (int i= 0; i < m; i++) { dsu::addedge(edges[i].u, edges[i].v); ans[trsz] = edges[i].w; } //build binlift memset(par, 0, sizeof(par)); memset(hadcan, 0, sizeof(hadcan)); h[trsz] = 1; dfs(trsz); // for (int i = 1; i <= trsz; i++) { // cout << i << ' ' << h[i] << ' ' << can[i] << ' ' << ans[i] << "\n"; // } } int getMinimumFuelCapacity(int X, int Y) { int x = X+1, y = Y+1; //lca int l = lca(x, y); //check if lca can if (can[l]) { return ans[l]; } //if not -> find nearest can l = findnearest(l); //case cannot if (!can[l]) return -1; return ans[l]; } #ifdef mikevui int main() { ios_base::sync_with_stdio(0); cin.tie(0); // #define name "task" // if (fopen(name".inp", "r")) { // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); // } int N, M; cin >> N >> M; vector<int> U, V, W; for (int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; U.pb(u); V.pb(v); W.pb(w); } init(N,M,U,V,W); int Q; cin >> Q; while (Q--) { int X, Y; cin >> X >> Y; cout << getMinimumFuelCapacity(X,Y) << "\n"; } } #endif // mikevui /* 5 6 0 1 4 0 2 4 1 2 1 1 3 2 1 4 10 2 3 3 3 1 2 2 4 0 1 3 2 0 1 5 0 2 5 1 1 2 */
#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...