Submission #1225841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225841		KALARRY	Swapping Cities (APIO20_swap)	C++20	100 / 100	503 ms	402900 KiB

swap

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int n,m,min_good[500005],s[500005],p[500005],deg[500005],Nodes,up[500005][20],up_max[500005][20],tin[500005],tout[500005],timer;
stack<int> cur_elem[500005];
bool is_good[500005];
vector<pair<int,int>> adj[500005];


int find_Sett(int i)
{
    if(p[i]==i)
        return p[i];
    p[i] = find_Sett(p[i]);
    return p[i];
}


bool is_Same_Sett(int i,int j)
{
    return find_Sett(i)==find_Sett(j);
}

void union_Sett(int i,int j,int w,bool after)
{
    int x = find_Sett(i);
    int y = find_Sett(j);
    deg[i]++;
    deg[j]++;
    if(deg[i] > 2)
        is_good[x] = true;
    if(deg[j] > 2)
        is_good[y] = true;
    if(is_Same_Sett(i,j))
        is_good[x] = true;
    else
    {
        if(s[x] < s[y])
            swap(x,y);
        p[y] = x;
        s[x] += s[y];
        is_good[x] |= is_good[y];
        if(cur_elem[y].size() > cur_elem[x].size())
            swap(cur_elem[x],cur_elem[y]);
        while(!cur_elem[y].empty())
        {
            int k = cur_elem[y].top();
            cur_elem[y].pop();
            cur_elem[x].push(k);
        }
        if(!after)
        {
            Nodes++;
            adj[x].push_back({Nodes,w});
            adj[y].push_back({Nodes,w});
            adj[Nodes].push_back({x,w});
            adj[Nodes].push_back({y,w});
            p[x] = Nodes;
            p[y] = Nodes;
            p[Nodes] = Nodes;
            s[Nodes] = s[x];
            is_good[Nodes] = is_good[x];
            swap(cur_elem[Nodes],cur_elem[x]);
            x = Nodes;
        }
    }
    if(is_good[x])
    {
        while(!cur_elem[x].empty())
        {
            int k = cur_elem[x].top();
            cur_elem[x].pop();
            min_good[k] = w;
        }
    }
}

pair<int,pair<int,int>> edges[200005];

void dfs(int v,int par,int par_w)
{
    tin[v] = ++timer;
    up[v][0] = par;
    up_max[v][0] = par_w;
    for(int L = 1 ; L <= 18 ; L++)
    {
        up[v][L] = up[up[v][L-1]][L-1];
        up_max[v][L] = max(up_max[v][L-1],up_max[up[v][L-1]][L-1]);
    }
    for(auto e : adj[v])
    {
        int u = e.first;
        int w = e.second;
        if(u != par)
            dfs(u,v,w);
    }
    tout[v] = ++timer;
}

bool is_ancestor(int a,int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int LCA(int a,int b)
{
    if(is_ancestor(a,b))
        return a;
    for(int L = 18 ; L >= 0 ; L--)
        while(!is_ancestor(up[a][L],b))
            a = up[a][L];
    a = up[a][0];
    return a;
}

int anc_dist(int a,int b)
{
    if(is_ancestor(b,a))
        return 0;
    int ret = 0;
    for(int L = 18 ; L >= 0 ; L--)
        while (!is_ancestor(up[b][L],a))
        {
            ret = max(ret,up_max[b][L]);
            b = up[b][L];
        }
    ret = max(ret,up_max[b][0]);
    return ret;
}

int min_dist(int a,int b)
{
    int lca = LCA(a,b);
    int ret = max(anc_dist(lca,a),anc_dist(lca,b));
    return ret;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;
    Nodes = N;
    for(int i = 1 ; i <= N ; i++)
    {
        p[i] = i;
        s[i] = 1;
        min_good[i] = -1;
        cur_elem[i].push(i);
    }
    for(int i = 1 ; i <= M ; i++)
        edges[i]  = {W[i-1],{V[i-1]+1,U[i-1]+1}};
    sort(edges+1,edges+M+1);
    for(int v,u,w,i = 1 ; i <= M ; i++)
    {
        v = edges[i].second.first;
        u = edges[i].second.second;
        w = edges[i].first;
        union_Sett(v,u,w,false);
    }
    dfs(Nodes,Nodes,0);
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;
    int ret = min_good[X];
    if(ret==-1)
        return -1;
    ret = max(ret,min_dist(X,Y));
    return ret;
}

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