Submission #978201

#	Time	Username	Problem	Language	Result	Execution time	Memory
978201		irmuun	Swapping Cities (APIO20_swap)	C++17	30 / 100	527 ms	524288 KiB

swap

#include<bits/stdc++.h>
#include "swap.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=1e5+5;

vector<int>cost(N,2e9);
vector<pair<int,int>>adj[N];
int par[N][20],P[N],dep[N],C[N][20];

void calc(int a,int b,int c){
    cost[a]=min(cost[a],max(cost[b],c));
    cost[b]=min(cost[b],max(cost[a],c));
}

void up(int x,int p){//direction
    P[x]=p;
    for(auto [y,w]:adj[x]){
        if(y!=p){
            C[y][0]=w;
            dep[y]=dep[x]+1;
            up(y,x);
            calc(x,y,w);
        }
    }
}
void down(int x,int p){
    for(auto [y,w]:adj[x]){
        if(y!=p){
            calc(x,y,w);
            down(y,x);
        }
    }
}

int find(int x,int d){
    for(int i=19;i>=0;i--){
        if(d&(1<<i)){
            x=par[x][i];
        }
    }
    return x;
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    x=find(x,dep[x]-dep[y]);
    for(int i=19;i>=0;i--){
        if(par[x][i]!=par[y][i]){
            x=par[x][i];
            y=par[y][i];
        }
    }
    if(x==y) return x;
    return par[x][0];
}
int f(int x,int d){
    int res=0;
    for(int i=19;i>=0;i--){
        if(d&(1<<i)){
            res=max(res,C[x][i]);
            x=par[x][i];
        }
    }
    return res;
}

void init(int n,int m,vector<int>u,vector<int>v,vector<int>w){
    for(int i=0;i<n;i++){
        for(int j=0;j<20;j++){
            C[i][j]=2e9;
        }
    }
    for(int i=0;i<m;i++){
        adj[u[i]].pb({v[i],w[i]});
        adj[v[i]].pb({u[i],w[i]});
    }
    for(int i=0;i<n;i++){
        if(adj[i].size()>=3){
            vector<int>edge;
            for(auto [j,W]:adj[i]){
                edge.pb(W);
            }
            sort(all(edge));
            cost[i]=edge[2];
        }
    }
    dep[0]=0;
    up(0,-1);
    down(0,-1);
    for(int i=0;i<n;i++){
        par[i][0]=P[i];
    }
    par[0][0]=0;
    for(int j=1;j<20;j++){
        for(int i=0;i<n;i++){
            par[i][j]=par[par[i][j-1]][j-1];
            C[i][j]=max(C[par[i][j-1]][j-1],C[i][j-1]);
        }
    }
}

int getMinimumFuelCapacity(int x,int y){
    int l=lca(x,y);
    int d=max(f(x,dep[x]-dep[l]),f(y,dep[y]-dep[l]));
    d=max(cost[x],d);
    if(d==2e9) d=-1;
    return d;
}

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