Submission #788048

#TimeUsernameProblemLanguageResultExecution timeMemory
788048ToniBSwapping Cities (APIO20_swap)C++17
6 / 100
113 ms19176 KiB
#include <bits/stdc++.h> #include "swap.h" #define X first #define Y second using namespace std; typedef pair<int, int> pii; const int MAXN = 1e5 + 2; const int LOG = 18; int n, m, cycle[MAXN], uf[MAXN], sz[MAXN], cnt[MAXN]; int dep[MAXN], bl[MAXN][LOG], bl_w[MAXN][LOG]; bool uf_bio[MAXN]; vector<pair<int, int> > adj[MAXN], tree[MAXN]; vector<pair<int, pii> > edges; int f(int x){ while(uf[x] != -1) x = uf[x]; return x; } void join(int u, int v, int edge){ if(uf_bio[u] ^ uf_bio[v]){ if(uf_bio[v]) swap(u, v); cycle[v] = edge; uf_bio[v] = 1; } if(sz[u] > sz[v]) swap(u, v); sz[v] += sz[u]; uf[u] = v; } int calc(int u, int v){ if(dep[u] < dep[v]) swap(u, v); int ret = 0, lift = u; for(int i = 0; i < LOG; ++i){ if(dep[u] - dep[v] & 1 << i){ ret = max(ret, bl_w[lift][i]); lift = bl[lift][i]; } } u = lift; if(u == v) return ret; for(int i = LOG - 1; i >= 0; --i){ if(bl[u][i] != bl[v][i]){ ret = max(ret, bl_w[u][i]); ret = max(ret, bl_w[v][i]); u = bl[u][i]; v = bl[v][i]; } } ret = max(ret, bl_w[u][0]); ret = max(ret, bl_w[v][0]); return ret; } void dfs(int node, int anc, int edge = 0){ bl[node][0] = anc; bl_w[node][0] = edge; dep[node] = dep[anc] + 1; for(pii x : tree[node]){ if(x.X == anc) continue; dfs(x.X, node, x.Y); } } void connect(int node, int edge){ if(!uf_bio[node]){ uf_bio[node] = 1; cycle[node] = edge; } } void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w){ n = _n; m = _m; for(int i = 0; i < n; ++i){ uf[i] = -1; sz[i] = 1; } for(int i = 0; i < m; ++i){ adj[u[i]].push_back({v[i], w[i]}); adj[v[i]].push_back({u[i], w[i]}); edges.push_back({w[i], {u[i], v[i]}}); } sort(edges.begin(), edges.end()); for(auto p : edges){ int u = p.Y.X, v = p.Y.Y; ++cnt[u]; ++cnt[v]; int fu = f(u), fv = f(v); if(cnt[u] >= 3) connect(fu, p.X); if(cnt[v] >= 3) connect(fv, p.X); u = fu; v = fv; if(u == v){ connect(u, p.X); } else { join(u, v, p.X); tree[p.Y.X].push_back({p.Y.Y, p.X}); tree[p.Y.Y].push_back({p.Y.X, p.X}); } } // // for(int i = 0; i < n; ++i){ // int node = i; // while(node != -1 && !uf_bio[node]){ // node = uf[node]; // } // if(node != -1) cycle[i] = cycle[node]; // } // // dfs(0, 0); // // for(int j = 1; j < n; ++j){ // for(int i = 0; i < n; ++i){ // bl[i][j] = bl[bl[i][j - 1]][j - 1]; // bl_w[i][j] = max(bl_w[i][j - 1], bl_w[bl[i][j - 1]][j - 1]); // } // } } int getMinimumFuelCapacity(int x, int y){ if(m + 1 == n) return -1; return edges[m - 1].X; if(min(cycle[x], cycle[y]) == 0) return -1; int val = calc(x, y); return max(val, min(cycle[x], cycle[y])); }

Compilation message (stderr)

swap.cpp: In function 'int calc(int, int)':
swap.cpp:35:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |   if(dep[u] - dep[v] & 1 << 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...