제출 #980342

#제출 시각아이디문제언어결과실행 시간메모리
980342hasan2006자매 도시 (APIO20_swap)C++17
36 / 100
432 ms128192 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N =2e5 + 9 , mod = 1e9 + 7; ll p[N], sz[N] , a[N] , b[N] , dp[N] , dp1[N] , c[N][25] , d[N] , par[N][25] , mx[N][25] , us[N] , us1[N]; vector<pair<ll,ll>>v[N] , v1[N] , vc[N] , vv[N]; int get(int x){ return (p[x] == x ? x : get(p[x])); } void join(int X , int Y , ll k){ int x = get(X) , y = get(Y); if(x != y){ if(sz[x] < sz[y]) swap(x , y); p[y] = x; sz[x] += sz[y]; vv[X].pb({k , Y}); vv[Y].pb({k , X}); }else { v1[X].pb({k , Y}); v1[Y].pb({k , X}); } } ll timer = 0; void dd(int n ,int p = 0 , int k = 0){ if(p) v[p].pb({k , n}); for(auto to : vv[n]) if(to.se != p) dd(to.se , n , to.fi); } void dfs(int n , int p = 0 , ll k = 1e18){ par[n][0] = p; if(v[p].size()) c[n][0] = v[p][0].fi; else c[n][0] = 1e18; if(v[p].size() && v[p][0].se == n){ if(v[p].size() > 1) c[n][0] = v[p][1].fi; else c[n][0] = 1e18; } if(v1[p].size()) c[n][0] = min(c[n][0] , v1[p][0].fi); if(v1[n].size()) c[n][0] = min(c[n][0] , v1[n][0].fi); mx[n][0] = k; us[n] = ++timer; for(int i = 1; i <= 20; i++){ par[n][i] = par[par[n][i - 1]][i - 1] ; mx[n][i] = max(mx[n][i - 1] , mx[par[n][i - 1]][i - 1]); c[n][i] = min(c[n][i - 1] , c[par[n][i - 1]][i - 1]); } for(auto to : v[n]) dfs(to.se , n , to.fi); if(v1[n].size()) dp[n] = min(dp[n] , v1[n][0].fi); if(v[n].size() > 1) dp[n] = min(dp[n] , v[n][1].fi); dp[p] = min(dp[p] , max(k , dp[n])); us1[n] = ++timer; } void dfs1(int n , int p = 0 , ll k = 1e18 , ll ans = 1e18){ if(v1[n].size()) ans = min(ans , v1[n][0].fi); dp1[n] = ans; v[n].pb({k , p}); for(auto to : v[n]) if(to.se != p) vc[n].pb({max(to.fi , dp[to.se]) , to.se}); sort(all(v[n])); sort(all(vc[n])); for(auto to : v[n]){ if(to.se != p){ ll ans1 = ans; if(v[n].size() >= 3){ if(v[n][1].se == to.se || v[n][0].se == to.se) ans1 = min(ans1, v[n][2].fi); else ans1 = min(ans1 , v[n][1].fi); } if(vc[n][0].se != to.se) ans1 = min(ans1 ,vc[n][0].fi); else if(vc[n].size() > 1) ans1 = min(ans1 , vc[n][1].fi); dfs1(to.se , n , to.fi , max(ans1 , to.fi)); } } } bool ok(int u, int v) { return (u == 0 || (us[u] <= us[v] && us1[u] >= us1[v])); } ll get(int x , int y){ ll mn = 1e18 , ans = 0; mn = min({mn , dp[y]}); for(int i = 18; i >= 0; i--){ if(!ok(par[y][i] , x)){ mn = min(mn , c[y][i]); ans = max(ans , mx[y][i]); y = par[y][i]; } } ans = max(ans , mx[y][0]); mn = min({mn , dp1[y]}); ans = max(ans , mn); if(ans > 1e9) ans = -1; return ans; } ll mm = 0; ll lca(int x , int y){ if(ok(x , y)){ return get(x , y); } if(ok(y , x)) return get(y , x); ll mn = 1e18 , ans = 0; mn = min({mn , dp[x] , dp[y]}); for(int i = 18; i >= 0; i--){ if(!ok(par[y][i] , x)){ mn = min(mn , c[y][i]); ans = max(ans , mx[y][i]); y = par[y][i]; } } for(int i = 18; i >= 0; i--){ if(!ok(par[x][i] , y)){ mn = min(mn , c[x][i]); ans = max(ans , mx[x][i]); x = par[x][i]; } } ans = max(ans , mx[x][0]); ans = max(ans , mx[y][0]); for(int i = 0; i < 3 && i < v[par[x][0]].size(); i++) if(v[par[x][0]][i].se != x && v[par[x][0]][i].se != y) mn = min(mn ,v[par[x][0]][i].fi); x = par[x][0]; if(v1[x].size()) mn = min(mn , v1[x][0].fi); ans = max(ans , mn); if(ans > 1e9) ans = -1; return ans; } void init(int n , int m , vector<int>v , vector<int>u , vector<int>c) { vector<pair<ll,pair<ll,ll>>>vc; for(int i = 0; i <= n; i++) dp[i] = 1e18 , p[i] = i , sz[i] = 1; for(int i = 0; i < m; i++) vc.pb({c[i] , {v[i] + 1, u[i] + 1}}); sort(all(vc)); for(auto to : vc) join(to.se.fi , to.se.se , to.fi); dd(1); for(int i = 1; i <= n ; i++) sort(all(::v[i])) , sort(rall(::v1[i])); dfs(1); dfs1(1); } int getMinimumFuelCapacity(int l, int r) { l++ , r++; return lca(l , r); } /* int main(){ init(4, 4, {0, 0, 1 , 2}, {1 , 3 , 2 , 3}, {1 , 3 , 2 , 4}); cout<<getMinimumFuelCapacity(0,1)<<"\n"; cout<<getMinimumFuelCapacity(0,2)<<"\n"; cout<<getMinimumFuelCapacity(0,3)<<"\n"; cout<<getMinimumFuelCapacity(1,2)<<"\n"; cout<<getMinimumFuelCapacity(1,3)<<"\n"; cout<<getMinimumFuelCapacity(2,3)<<"\n"; }*/

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'long long int lca(int, int)':
swap.cpp:161:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int i = 0; i < 3 && i < v[par[x][0]].size(); 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...