Submission #865061

#	Time	Username	Problem	Language	Result	Execution time	Memory
865061		jk410	Swapping Cities (APIO20_swap)	C++17	100 / 100	213 ms	66540 KiB

swap

#include "swap.h"
#include <vector>
#include <algorithm>
#include <functional>
#define all(v) v.begin(),v.end()
using namespace std;
struct edge{
    int u,v,cost;
};
struct node{
    int cost;
    bool flag;
};
const int MAX=18;
vector<node> nodes;
vector<vector<int>> child;
vector<int> depth;
vector<vector<int>> par(MAX+1);
vector<int> ans;
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    vector<edge> edges(M);
    vector<int> group(N+M);
    vector<int> deg(N);
    nodes.resize(N+M);
    child.resize(N+M);
    depth.resize(N+M);
    for (int i=0; i<=MAX; i++)
        par[i].resize(N+M);
    ans.resize(N+M);
    for (int i=0; i<M; i++)
        edges[i]={U[i],V[i],W[i]};
    sort(all(edges),[&](edge a,edge b)->bool{
        return a.cost<b.cost;
    });
    for (int i=0; i<N+M; i++){
        group[i]=i;
        nodes[i]={0,false};
        par[0][i]=i;
    }
    function<int(int)> getGroup=[&](int v)->int{
        if (group[v]==v)
            return v;
        return group[v]=getGroup(group[v]);
    };
    for (int i=0; i<M; i++){
        edge e=edges[i];
        nodes[i+N].cost=e.cost;
        deg[e.u]++;
        deg[e.v]++;
        int u=getGroup(e.u),v=getGroup(e.v);
        if (deg[e.u]>2||deg[e.v]>2||nodes[u].flag||nodes[v].flag)
            nodes[i+N].flag=true;
        if (u==v){
            group[u]=i+N;
            child[i+N].push_back(u);
            par[0][u]=i+N;
            nodes[i+N].flag=true;
            continue;
        }
        group[u]=group[v]=i+N;
        child[i+N].push_back(u);
        child[i+N].push_back(v);
        par[0][u]=par[0][v]=i+N;
    }
    for (int t=1; t<=MAX; t++){
        for (int i=0; i<N+M; i++)
            par[t][i]=par[t-1][par[t-1][i]];
    }
    function<void(int)> dfs=[&](int v){
        for (int i:child[v]){
            depth[i]=depth[v]+1;
            ans[i]=(nodes[i].flag?nodes[i].cost:ans[v]);
            dfs(i);
        }
    };
    for (int i=0; i<N+M; i++){
        if (par[0][i]!=i)
            continue;
        ans[i]=(nodes[i].flag?nodes[i].cost:-1);
        dfs(i);
    }
}
int getLCA(int u,int v){
    if (depth[u]>depth[v])
        swap(u,v);
    for (int i=0,t=depth[v]-depth[u]; t; i++,t>>=1){
        if (t&1)
            v=par[i][v];
    }
    if (u==v)
        return u;
    for (int t=MAX; t>=0; t--){
        if (par[t][u]!=par[t][v]){
            u=par[t][u];
            v=par[t][v];
        }
    }
    return par[0][u];
}
int getMinimumFuelCapacity(int X, int Y){
    return ans[getLCA(X,Y)];
}

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