Submission #1199721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199721		guagua0407	Swapping Cities (APIO20_swap)	C++20	0 / 100	507 ms	62752 KiB

swap

#include "swap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int inf=1e9;
    const int mxn=1e5+5;
    vector<int> U,V,W;
    vector<int> mn(mxn,inf);
    vector<vector<pair<int,int>>> adj(mxn);
    vector<vector<int>> up(mxn,vector<int>(20));
    vector<vector<int>> mx(mxn,vector<int>(20));
    vector<vector<int>> upmn(mxn,vector<int>(20));
    vector<multiset<int>> ch(mxn);
    vector<int> pid(mxn,-1);
    vector<int> d(mxn);
    struct DSU{
        vector<int> e;
        DSU(int n){
            e=vector<int>(n,-1);
        }
        int find(int x){
            return (e[x]<0?x:e[x]=find(e[x]));
        }
        bool unite(int a,int b){
            a=find(a);
            b=find(b);
            if(a==b) return false;
            if(e[a]>e[b]) swap(a,b);
            e[a]+=e[b];
            e[b]=a;
            return true;
        }
    };
    int go(int x,int len){
        for(int i=0;i<20;i++){
            if(len&(1<<i)){
                x=up[x][i];
            }
        }
        return x;
    }
    pair<int,int> lca(int a,int b){
        if(d[a]<d[b]) swap(a,b);
        int len=d[a]-d[b];
        int ans=0;
        for(int i=0;i<20;i++){
            if(len&(1<<i)){
                ans=max(ans,mx[a][i]);
                a=up[a][i];
            }
        }
        if(a==b) return make_pair(a,ans);
        for(int i=19;i>=0;i--){
            int ta=up[a][i];
            int tb=up[b][i];
            if(ta!=tb){
                ans=max(ans,mx[a][i]);
                ans=max(ans,mx[b][i]);
                a=tb;
                b=tb;
            }
        }
        ans=max({ans,mx[a][0],mx[b][0]});
        return make_pair(up[a][0],ans);
    }
    int path(int a,int b){
        if(a==b) return inf;
        int x=a;
        int ans=inf;
        for(int i=19;i>=0;i--){
            int y=up[x][i];
            if(d[y]>d[b]){
                ans=min(ans,upmn[x][i]);
                x=up[x][i];
            }
        }
        //cout<<a<<' '<<b<<' '<<ans<<'\n';
        return ans;
    }
    int val(int a){
        int ans=mn[a];
        for(auto v:adj[a]){
            if(v.f==up[a][0]) continue;
            ans=min(ans,W[v.s]);
        }
        return ans;
    }
}

void init(int n, int m,
          std::vector<int> u, std::vector<int> v, std::vector<int> w) {
    U=u;
    V=v;
    W=w;
    vector<pair<int,int>> e(m);
    for(int i=0;i<m;i++){
        e[i]={W[i],i};
    }
    sort(all(e));
    vector<bool> tree(m);
    DSU dsu(n);
    for(int i=0;i<m;i++){
        int id=e[i].s;
        if(dsu.unite(U[id],V[id])){
            tree[id]=true;
            //cout<<U[id]<<' '<<V[id]<<'\n';
        }
    }
    for(int i=0;i<m;i++){
        U[i]++;
        V[i]++;
    }
    for(int i=0;i<m;i++){
        if(!tree[i]){
            mn[U[i]]=min(mn[U[i]],W[i]);
            mn[V[i]]=min(mn[V[i]],W[i]);
            continue;
        }
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    for(int i=0;i<=n;i++){
        ch[i].insert(inf);
    }
    function<void(int,int)> dfs=[&](int v,int p){
        for(auto u:adj[v]){
            if(u.f==p) continue;
            d[u.f]=d[v]+1;
            ch[v].insert(W[u.s]);
            dfs(u.f,v);
            up[u.f][0]=v;
            pid[u.f]=u.s;
            mx[u.f][0]=W[u.s];
        }
    };
    dfs(1,0);
    upmn[1][0]=inf;
    for(int i=2;i<=n;i++){
        ch[up[i][0]].erase(ch[up[i][0]].find(W[pid[i]]));
        upmn[i][0]=min(mn[up[i][0]],*ch[up[i][0]].begin());
        ch[up[i][0]].insert(W[pid[i]]);
    }
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            up[i][j]=up[up[i][j-1]][j-1];
            mx[i][j]=max(mx[i][j-1],mx[up[i][j-1]][j-1]);
            upmn[i][j]=min(upmn[i][j-1],upmn[up[i][j-1]][j-1]);
        }
    }
}

int getMinimumFuelCapacity(int a, int b) {
    a++;
    b++;
    if(d[a]<d[b]) swap(a,b);
    pair<int,int> p=lca(a,b);
    int c=p.f;
    int val=p.s;
    int ans=inf;
    if(c==b){
        ans=min(ans,path(a,b));
        //ans=min(ans,val(a));
        if(pid[b]!=-1){
            //ans=min(ans,W[pid[b]]);
        }
    }
    else{
        int A=go(a,d[a]-d[c]-1);
        int B=go(b,d[b]-d[c]-1);
        ans=min(ans,path(a,c));
        ans=min(ans,path(b,c));
        //ans=min(ans,val(a));
        //ans=min(ans,val(b));
        ch[c].erase(ch[c].find(W[pid[A]]));
        ch[c].erase(ch[c].find(W[pid[B]]));
        ans=min(ans,*ch[c].begin());
        ch[c].insert(W[pid[A]]);
        ch[c].insert(W[pid[B]]);
        if(c!=1) ans=min(ans,W[pid[c]]);
    }
    return (ans==inf?-1:max(ans,val));
}

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