Submission #982110

#	Time	Username	Problem	Language	Result	Execution time	Memory
982110		Abito	Swapping Cities (APIO20_swap)	C++17	7 / 100	456 ms	524288 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ep insert
#define pb push_back
using namespace std;
const int NN=4e5+5;
int n,m,c,C=INT_MAX,dis[NN],lg[NN],f[NN];
vector<pair<int,int>> adj[NN];
pair<int,int> st[25][NN],par[25][NN];
bool cmp(pair<int,int> x,pair<int,int> y){
    return x.S<y.S;
}
void dfs(int x,int p){
    dis[x]=dis[p]+1;
    st[0][++c]={dis[x],x};
    f[x]=c;
    for (auto u:adj[x]){
        if (u.F==p) continue;
        par[0][u.F]={x,u.S};
        dfs(u.F,x);
        st[0][++c]={dis[x],x};
    }return;
}
void build(){
    for (int i=1;i<25;i++) for (int j=1;j+(1<<i)<=2*n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    for (int i=1;i<25;i++){
        for (int j=1;j<=n;j++){
            par[i][j].F=par[i-1][par[i-1][j].F].F;
            par[i][j].S=max(par[i-1][j].S,par[i-1][par[i-1][j].F].S);
        }
    }return;
}
int query(int l,int r){
    if (l>r) swap(l,r);
    int i=lg[r-l+1];
    return min(st[i][l],st[i][r-(1<<i)+1]).S;
}
void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {
    for (int i=2;i<NN;i++) lg[i]=lg[i/2]+1;
    n=N,m=M;dis[0]=-1;
    for (int i=0;i<m;i++){
        adj[U[i]+1].pb({V[i]+1,W[i]});
        adj[V[i]+1].pb({U[i]+1,W[i]});
    }
    for (int i=1;i<=n;i++){
        if (adj[i].size()<3) continue;
        sort(adj[i].begin(),adj[i].end(),cmp);
        C=min(C,adj[i][2].S);
    }
    dfs(1,0);
    build();
    return;
}

int getMinimumFuelCapacity(int x, int y) {
    x++;y++;
    int lca=query(f[x],f[y]);
    int ans=C,ansx=0,ansy=0;
    for (int i=0;i<25;i++) if ((dis[x]-dis[lca])&(1<<i)) ansx=max(ansx,par[i][x].S),x=par[i][x].F;
    for (int i=0;i<25;i++) if ((dis[y]-dis[lca])&(1<<i)) ansy=max(ansy,par[i][y].S),y=par[i][y].F;
    ans=max(ans,max(ansx,ansy));
    if (ans==INT_MAX) return -1;
    return ans;
}

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