Submission #1231592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231592		CELD_07	Swapping Cities (APIO20_swap)	C++20	0 / 100	163 ms	104228 KiB

swap

#include "swap.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) //cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<pair<ll, ll>>> adj, adj1, up, up1;
vector<ll> s, p, dist, v, v1, v2, in, ou;
inline ll _find(ll n){
if(p[n]!=n){p[n]=_find(p[n]);return p[n];}
return n;
}
inline void _union(ll a, ll b, ll w){
a=_find(a);
b=_find(b);
if(a==b)return;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
if(s[a]<s[b])swap(a, b);
s[a]+=s[b];
p[b]=a;
}
ll cnt=0;
inline void dfs(ll n, ll p, ll w, ll w1){
in[n]=cnt;
cnt++;
for(auto& [x, y]: adj1[n]){
if(x==p)continue;
if(y<v[n]){v2[n]=v1[n];v1[n]=v[n];v[n]=y;}
else if(y<v1[n]){v2[n]=v1[n];v1[n]=y;}
else if(y<v2[n])v2[n]=y;
}
up[n][0].ft=p;
up1[n][0].ft=p;
up[n][0].sd=w;
up1[n][0].sd=w1;
for(int i=1; i<24; i++){
if(up[n][i-1].ft!=-1 && up[up[n][i-1].ft][i-1].ft!=-1){
up[n][i].ft=up1[n][i].ft=up[up[n][i-1].ft][i-1].ft;
up[n][i].sd=max(up[n][i-1].sd, up[up[n][i-1].ft][i-1].sd);
up1[n][i].sd=min(up1[n][i-1].sd, up1[up1[n][i-1].ft][i-1].sd);
}
}
for(auto& [x, y]: adj[n]){
if(x==p)continue;
dist[x]=dist[n]+1;
dfs(x, n, y, (y==v[n] ? v1[n] : v[n]));
}

if(w<v[n]){v2[n]=v1[n];v1[n]=v[n];v[n]=w;}
else if(w<v1[n]){v2[n]=v1[n];v1[n]=w;}
else if(w<v2[n])v2[n]=w;
ou[n]=cnt;
cnt++;
}
inline ll query(ll a, ll b, bool n){
ll o=LLONG_MIN, o1=LLONG_MAX;
if(dist[a]<dist[b])swap(a, b);
for(int i=22; i>=0; i--){
if(up[a][i].ft!=-1 && dist[up[a][i].ft]>dist[b]){
o=max(o, up[a][i].sd);
o1=min(o1, up1[a][i].sd);
a=up[a][i].ft;
}
}
//cout<<a<<" "<<o<<" "<<o1<<endl;
if((dist[a]!=dist[b] ? up[a][0].ft : a)==b)return max(max(o, up[a][0].sd), o1);
if(dist[a]>dist[b]){
o=max(o, up[a][0].sd);
o1=min(o1, up1[a][0].sd);
a=up[a][0].ft;
}
for(int i=22; i>=0; i--){
if(up[a][i].ft!=up[b][i].ft){
o=max({o, up[a][i].sd, up[b][i].sd});
o1=min({o1, up1[a][i].sd, up1[b][i].sd});
a=up[a][i].ft;
b=up[b][i].ft;
}
}
o=max({o, up[a][0].sd, up[b][0].sd});
if(min(up[a][0].sd, up[b][0].sd)==v[up[a][0].ft] && max(up[a][0].sd, up[b][0].sd)==v1[up[a][0].ft])o1=min({o1, v2[up[a][0].ft]});
else if(min(up[a][0].sd, up[b][0].sd)==v[up[a][0].ft] && max(up[a][0].sd, up[b][0].sd)>=v2[up[a][0].ft])o1=min({o1, v1[up[a][0].ft]});
else o1=min({o1, v[up[a][0].ft]});
//cout<<up[a][0].ft<<" "<<o<<" "<<o1<<endl;
return max(o,o1);
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<vector<pair<ll, ll>>>().swap(adj);
vector<vector<pair<ll, ll>>>().swap(adj1);
vector<vector<pair<ll, ll>>>().swap(up);
vector<vector<pair<ll, ll>>>().swap(up1);
vector<ll>().swap(p);
vector<ll>().swap(s);
vector<ll>().swap(v);
vector<ll>().swap(v1);
vector<ll>().swap(v2);
vector<ll>().swap(in);
vector<ll>().swap(ou);
vector<ll>().swap(dist);
dist.assign(N+1, 0);
in.resize(N+1);
ou.resize(N+1);
cnt=0;
v2.assign(N+1, LLONG_MAX);
v.assign(N+1, LLONG_MAX);
v1.assign(N+1, LLONG_MAX);
up.assign(N+1, vector<pair<ll, ll>>(24, {-1, LLONG_MAX}));
up1.assign(N+1, vector<pair<ll, ll>>(24, {-1, LLONG_MAX}));
adj.resize(N+1);
p.resize(N+1);
s.assign(N+1, 1);
adj1.resize(N+1);
iota(all(p), 0);
vector<tuple<ll, ll, ll>> v1;
for(int i=0; i<M; i++){
adj1[V[i]].push_back({U[i], W[i]});
adj1[U[i]].push_back({V[i], W[i]});
v1.push_back({W[i], V[i], U[i]});
}
sort(all(v1));
for(auto& [x, y, z]: v1)_union(z, y, x);
dfs(0, -1, LLONG_MAX, LLONG_MAX);
/*
for(int i=0; i<N; i++){
cout<<i<<endl;
for(int j=0; j<=5; j++){
cout<<up[i][j].ft<<" : "<<(up1[i][j].sd!=LLONG_MAX ? up1[i][j].sd : -1)<<" ";
}
cout<<endl;
}*/
}

int getMinimumFuelCapacity(int X, int Y) {
    ll res=LLONG_MAX;
    res=min(res, query(X, Y, 1));
    /*for(auto& [x, y]: adj1[X]){
    if((in[X]<=in[x] && ou[X]>=ou[x]) && (in[X]>ou[Y] || ou[X]<in[Y]))continue;
    if((in[X]<=in[Y] && ou[X]>=ou[Y]) && (in[X]>ou[x] || ou[X]<in[x]))continue;
    if(x==up[X][0].ft)continue;
    //cout<<x<<" "<<y<<endl;
    res=min(res, max({y, query(x, Y, 0), o1}));
    }
    for(auto& [x, y]: adj1[Y]){
    if((in[Y]<=in[x] && ou[Y]>=ou[x]) && (in[Y]>ou[X] || ou[X]<in[X]))continue;
    if((in[Y]<=in[X] && ou[Y]>=ou[X]) && (in[Y]>ou[x] || ou[X]<in[x]))continue;
    if(x==up[Y][0].ft)continue;
    //cout<<x<<" "<<y<<endl;
    res=min(res, max({y, query(x, X, 0), o1}));
    }*/
  return (res!=LLONG_MAX ? res : -1);
}/*
int main(){
ll a, b, c;
cin>>a>>b;
vector<int> v(b), v1(b), v2(b);
for(int i=0; i<b; i++){
cin>>v[i]>>v1[i]>>v2[i];
}
init(a, b, v, v1, v2);
while(1){
cin>>a>>b;
cout<<getMinimumFuelCapacity(a, b)<<endl;
}
}*/

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27