Submission #1233836

#TimeUsernameProblemLanguageResultExecution timeMemory
1233836thelegendary08Swapping Cities (APIO20_swap)C++17
0 / 100
276 ms72896 KiB
#include "swap.h" #include<bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define f0r(i,n) for(signed i = 0; i<n; i++) #define FOR(i, k, n) for(signed i = k; i<n; i++) #define vi vector<int> #define vpii vector<pair<int,int>> #define pii pair<int,int> #define vb vector<bool> #define mii map<int,int> #define vvi vector<vector<int>> #define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl; #define dout(a) cout<<a<<' '<<#a<<endl; #define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl; using namespace std; struct edge{ int u, v, w; }; vector<vpii> adj; int n,m; vector<vi>edges; struct DSU{ int n; vi par, sz, hasthree, hascyc, rep; vi treepar, treesz, treea, treeb, weight, dep; vvi adj; int node_count; int m, lg; vvi jmp; DSU(){ } DSU(int N){ n = N; node_count = n; par.resize(n); sz.resize(n); hasthree.resize(n); hascyc.resize(n); f0r(i,n){ par[i] = i; sz[i] = 1; hasthree[i] = 0; hascyc[i] = 0; rep.pb(i); treepar.pb(-1); treesz.pb(1); treea.pb(0); treeb.pb(0); weight.pb(0); } } int find(int x){ while(x != par[x])x = par[x]; return x; } void unite(int a, int b, int w){ // dout2(a,b); a = find(a); b = find(b); if(a == b){ // dout(rep[a]); treepar[rep[a]] = node_count; treepar.pb(-1); treesz.pb(sz[a]); treea.pb(treea[a]); weight.pb(w); treeb.pb(1); rep[a] = node_count; node_count++; hascyc[a] = 1; // vout(treepar); return; } if(sz[a] < sz[b])swap(a,b); treepar[rep[a]] = node_count; treepar[rep[b]] = node_count; treepar.pb(-1); treesz.pb(sz[a] + sz[b]); treea.pb(hascyc[a] | hascyc[b]); treeb.pb(hasthree[a] | hasthree[b]); weight.pb(w); rep[a] = node_count; sz[a] += sz[b]; par[b] = a; hascyc[a] |= hascyc[b]; hasthree[a] |= hasthree[b]; node_count++; // vout(treepar); } void build_jmp(){ m = node_count; jmp.resize(m); lg = 0; for(int i = 62; i>=0; i--){ if((1LL << i) & m){ lg = i; break; } } lg++; f0r(i,m){ jmp[i].resize(lg); } f0r(i,m){ jmp[i][0] = treepar[i]; } // vout(treepar); FOR(i, 1, lg){ f0r(j, m){ if(jmp[j][i-1] == -1)jmp[j][i] = -1; else jmp[j][i] = jmp[jmp[j][i-1]][i-1]; } } adj.resize(m); f0r(i,m){ if(treepar[i] != -1)adj[treepar[i]].pb(i); } dep.resize(m); queue<int>q; q.push(m-1); while(!q.empty()){ int node = q.front(); q.pop(); for(auto u : adj[node]){ q.push(u); dep[u] = dep[node] + 1; } } } int lca(int a, int b){ if(dep[a] > dep[b])swap(a,b); int dif = dep[b] - dep[a]; f0r(i, lg){ if((1LL << i) & dif){ b = jmp[b][i]; } } for(int i = lg - 1; i>=0; i--){ if(jmp[a][i] != jmp[b][i]){ a = jmp[a][i]; b = jmp[b][i]; } } return treepar[a]; } int firstcan(int x){ if(treea[x] || treeb[x])return x; for(int i = lg-1; i>=0; i--){ if(!(treea[jmp[x][i]] || treeb[jmp[x][i]])){ x = jmp[x][i]; } } x = treepar[x]; return x; } }; vi dist; int l2; DSU d = DSU(); void init(signed N, signed M, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) { n = N; m = M; adj.resize(N); dist.resize(n); dist[0] = 4e18; f0r(i, M){ edges.pb({W[i], U[i], V[i]}); adj[U[i]].pb(mp(V[i], W[i])); adj[V[i]].pb(mp(U[i], W[i])); dist[V[i]] = W[i]; } sort(edges.begin(), edges.end()); d = DSU(n); f0r(i, M){ d.unite(edges[i][1], edges[i][2], edges[i][0]); } d.build_jmp(); } signed getMinimumFuelCapacity(signed X, signed Y) { if(n <= 3)return -1; // return 0; int l = d.lca(X, Y); return d.weight[d.firstcan(l)]; /* vi deg(n); DSU d = DSU(n); f0r(i, m){ d.unite(edges[i][1], edges[i][2]); deg[edges[i][1]]++; deg[edges[i][2]]++; int x = d.find(X); int y = d.find(Y); if(deg[edges[i][1]] == 3){ d.hasthree[d.find(edges[i][1])] = 1; } if(deg[edges[i][2]] == 3){ d.hasthree[d.find(edges[i][2])] = 1; } if(x == y && (d.hasthree[x] || d.hascyc[x])){ return edges[i][0]; } } return -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...