Submission #966828

#TimeUsernameProblemLanguageResultExecution timeMemory
966828AlperenT_Swapping Cities (APIO20_swap)C++14
6 / 100
397 ms76644 KiB
#include "swap.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #define pb push_back #define F first #define S second #define ld long double #define all(a) a.begin(),a.end() #define pii pair <int,int> #define ll long long #define PII pair<pii , pii> #define sz(v) (int)v.size() #define rep(i , a , b) for(int i=a;i <= (b);i++) #define per(i , a , b) for(int i=a;i >= (b);i--) #define deb(x) cout <<#x << " : " << x << "\n" ; using namespace std ; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 2e5+10 + 10, inf = 1e9+10 , mod = 1e9 + 7 , lg = 20 ; int cnt = 1 , par[maxn] , dis[maxn] , mark[maxn] , p[maxn][lg+1] , mn[maxn][lg+1] , mn2[maxn][lg+1] ; vector <pii> T[maxn] ; vector <pii> G[maxn]; set <pii> s[maxn] ; int find(int v){ if(par[v]==0)return v; return par[v] = find(par[v]) ; } void bui(int v , int r =0 ){ p[v][0] = r;mark[v] = 1; rep(i , 1 ,lg)p[v][i] = p[p[v][i-1]][i-1] ; for(auto [w,u] : T[v]){ if(u == r)continue ; bui(u,v); } } vector<int> tp; void dfs(int v, int r =0){ mark[v] =1 ; tp.pb(v); for(auto [w,u] : T[v]){ if(r == u)continue ; dis[u] = dis[v] + 1; mn2[u][0] = w; dfs(u , v) ; if(sz(s[u]) > sz(s[v]))swap(s[v],s[u]); while(sz(s[u])){ s[v].insert(*s[u].begin()); s[u].erase(s[u].begin()); } } for(auto [w,u] : G[v]){ if(dis[u] < dis[v]){ s[v].insert({w,u}) ; } } mn[v][0] = inf ; while(sz(s[v])){ int u =(*s[v].begin()).S , w = (*s[v].begin()).F ; if(dis[v]<=dis[u]){ s[v].erase(s[v].begin()); continue ; } mn[v][0] = w ; break ; } } pii up(int v ,int d){ int r = inf , r2 = 0; rep(i , 0 ,lg)if(d>>i&1){ r = min(r , mn[v][i]) ; r2= max(r2 , mn2[v][i]) ; v = p[v][i] ; } return (pii){r,r2}; } int up2(int v ,int d){ rep(i , 0 ,lg)if(d>>i&1){ v = p[v][i] ; } return v; } int lca2(int v, int u){ if(dis[v] < dis[u])swap(v,u); v = up2(v ,dis[v]-dis[u]) ; per(i , lg , 0){ if(p[v][i] != p[u][i]){ v = p[v][i] ; u = p[u][i] ; } } if(v==u)return v ; return p[v][0] ; } int lca(int v, int u){ if(dis[v] < dis[u])swap(v,u); pii a = up(v , dis[v]-dis[u]) ; v = up2(v,dis[v]-dis[u]) ; int a1 = a.F ,a2 =a.S; per(i , lg , 0){ if(p[v][i] != p[u][i]){ a1 = min({a1 ,mn[v][i] , mn[u][i]}); a2 = max({a2 ,mn2[v][i] , mn2[u][i]}) ; v = p[v][i] ; u = p[u][i] ; } } if(v==u)return max(a1 ,a2) ; a1 = min({a1 ,mn[v][0] , mn[u][0]}); a2 = max({a2 ,mn2[v][0] , mn2[u][0]}) ; return max(a1 ,a2); } int id[maxn] ; void init(int n, int m,vector<int>U, vector<int> V, vector<int> W) { vector<pair<int,pii> > ed; rep(i , 0 , m-1){ V[i]++;U[i]++; ed.pb({W[i] , {V[i],U[i]}}); } sort(all(ed)); rep(i , 0 ,sz(ed)-1){ int v = ed[i].S.F, u = ed[i].S.S , w = ed[i].F ; if(find(v) == find(u)){ id[i] = 1 ; }else{ par[find(v)] = find(u); T[v].pb({w,u}); T[u].pb({w,v}); } } rep(i ,1 , n){ if(mark[i] == 1)continue ; bui(i) ; } rep(i ,1 ,n)mark[i] =0 ; rep(i , 0 , sz(ed)-1){ if(id[i] == 1){ int w = ed[i].F , v =ed[i].S.F , u =ed[i].S.S ; int lc = lca2(v,u) ; G[v].pb({w,lc}); G[u].pb({w,lc}); } } rep(i ,1, n){ if(mark[i] == 1)continue ; dfs(i) ; } for(int v : tp){ rep(i , 1 ,lg){ p[v][i] = p[p[v][i-1]][i-1]; mn[v][i] = min(mn[v][i-1] , mn[p[v][i-1]][i-1]) ; mn2[v][i] = max(mn2[v][i-1] , mn2[p[v][i-1]][i-1]) ; } } } int getMinimumFuelCapacity(int v, int u) { v++ ;u++; if(find(v)!=find(u))return -1 ; int ans = lca(v,u); if(ans == inf)return -1 ; return ans; } /* g++ -Wall -lm -static -DEVAL -o swap -O2 swap.cpp grader.cpp -std=c++17 */

Compilation message (stderr)

swap.cpp: In function 'void bui(int, int)':
swap.cpp:33:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for(auto [w,u] : T[v]){
      |            ^
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:43:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |   for(auto [w,u] : T[v]){
      |            ^
swap.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   for(auto [w,u] : G[v]){
      |            ^
#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...