Submission #482997

#TimeUsernameProblemLanguageResultExecution timeMemory
482997PoPularPlusPlusSwapping Cities (APIO20_swap)C++17
17 / 100
106 ms41012 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pb(e) push_back(e) #define sv(a) sort(a.begin(),a.end()) #define sa(a,n) sort(a,a+n) #define mp(a,b) make_pair(a,b) #define vf first #define vs second #define ar array #define all(x) x.begin(),x.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const double PI=3.14159265358979323846264338327950288419716939937510582097494459230; bool remender(ll a , ll b){return a%b;} const int N = 100002 , M = 200003 , l = 25; vector<int> adj[M + N]; int degree[N]; int root , ans[N]; int timer; int tin[N], tout[N]; int up[N][l + 5]; void dfs(int v, int p){ tin[v] = ++timer; up[v][0] = p; for (int i = 1; i <= l; ++i) up[v][i] = up[up[v][i-1]][i-1]; for (int u : adj[v]) { if (u != p){ if(ans[u] == -1 && ans[v] != -1)ans[u] = ans[v]; dfs(u, v); } } tout[v] = ++timer; } bool is_ancestor(int u, int v){ return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int u, int v){ if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = l; i >= 0; --i) { if (!is_ancestor(up[u][i], v)) u = up[u][i]; } return up[u][0]; } struct UFDS { vector<int> p,siz; void init(int n){ p.resize(n + 2); siz.resize(n + 2); for(int i = 0; i <= n; i++){ p[i] = i; siz[i] = 1; } } int get(int x){ return p[x]=(x==p[x] ? x : get(p[x])); } void unio(int u , int v , int w , int a , int b){ // cycle if(a == b){ if(ans[a] == -1){ adj[root].pb(a); p[a] = root; degree[u]++; degree[v]++; ans[root] = w; } else return; } else { adj[root].pb(a); adj[root].pb(b); p[a] = root; p[b] = root; degree[u]++; degree[v]++; if(ans[a] != -1 || ans[b] != -1 || degree[u] == 3 || degree[v] == 3)ans[root] = w; } root++; } }; UFDS d; void init(int n , int m , vector<int> a , vector<int> b , vector<int> c){ memset(degree,0,sizeof degree); memset(ans,-1,sizeof ans); d.init(n + m + 2); timer = 0; root = n; vector<pair<int , pair<int,int>>> lol; for(int i = 0; i < m; i++){ lol.pb(mp(c[i] , mp(a[i] , b[i]))); //lol[b[i]].pb(mp(a[i] , c[i])); } sv(lol); for(int i = 0; i < m; i++){ d.unio(lol[i].vs.vf , lol[i].vs.vs , lol[i].vf , d.get(lol[i].vs.vf) , d.get(lol[i].vs.vs)); } dfs(root-1,root-1); } int getMinimumFuelCapacity(int x, int y){ int lc = lca(x , y); return ans[lc]; }
#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...