Submission #738247

#	Time	Username	Problem	Language	Result	Execution time	Memory
738247		PoonYaPat	Swapping Cities (APIO20_swap)	C++14	7 / 100	616 ms	64444 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,pg[100001],r[100001],lp[100001],LCA;
vector<pii> adj[100001];
vector<int> add[100001], del[100001];

struct Edge{
    int u,v,w;
    bool operator < (const Edge &o) {return w<o.w;}
};
vector<Edge> edge,bridge;

int find(int x) {
    while (pg[x]!=x) x=pg[x];
    return x;
}

void unite(int X, int Y, int w) {
    int x=find(X), y=find(Y);

    if (x!=y) {
        adj[X].push_back(pii(Y,w));
        adj[Y].push_back(pii(X,w));

        if (r[x]<r[y]) swap(x,y);
        pg[y]=x;
        if (r[x]==r[y]) ++r[x];
    } else {
        bridge.push_back({x,y,w});
    }
}

int p[100001][18],level[100001],mmin[100001][18],mmax[100001][18],mmi[100001][3],node[100001][2]; //mmi the 3 least subtree dge

void dfs1(int x, int par) {
    level[x]=level[par]+1;
    p[x][0]=par;
    for (int i=1; i<18; ++i) {
        p[x][i]=p[p[x][i-1]][i-1];
        mmax[x][i]=max(mmax[x][i-1],mmax[p[x][i-1]][i-1]);
    }

    mmi[x][0]=mmi[x][1]=mmi[x][2]=INT_MAX;
    priority_queue<pii, vector<pii>, greater<pii>> q;

    for (auto s : adj[x]) if (s.first!=par) q.push({s.second,s.first});

    if (q.size()) mmi[x][0]=q.top().first, node[x][0]=q.top().second, q.pop();
    if (q.size()) mmi[x][1]=q.top().first, node[x][1]=q.top().second, q.pop();
    if (q.size()) mmi[x][2]=q.top().first;


    for (auto s : adj[x]) if (s.first!=par) {
        if (s.first==node[x][0]) mmin[s.first][0]=mmi[x][1];
        else mmin[s.first][0]=mmi[x][0];
        mmax[s.first][0]=s.second;
        dfs1(s.first,x);
    }
}

void dfs2(int x, int par) {
    for (int i=1; i<18; ++i) mmin[x][i]=min(mmin[x][i-1],mmin[p[x][i-1]][i-1]);
    for (auto s : adj[x]) if (s.first!=par) dfs2(s.first,x);
}

int lca(int X, int Y, int mode) {
    int ma=-INT_MAX;
    if (level[X]<level[Y]) swap(X,Y);
    int x=X, y=Y;

    int dif=level[x]-level[y];
    for (int i=0; i<18; ++i) {
        if (dif&(1<<i)) {
            ma=max(ma,mmax[x][i]);
            x=p[x][i];
        }
    }

    if (x==y) {
        x=X; y=Y;
        --dif;
        int mi=min(lp[X],lp[Y]);
        mi=min(mi,mmi[X][1]);

        for (int i=0; i<18; ++i) {
            if (dif&(1<<i)) {
                mi=min(mi,mmin[x][i]);
                x=p[x][i];
            }
        }

        vector<int> h;
        h.push_back(mmax[Y][0]);
        if (x==node[Y][0]) {
            h.push_back(mmi[Y][1]);
            h.push_back(mmi[Y][2]);
        } else if (x==node[Y][1]) {
            h.push_back(mmi[Y][0]);
            h.push_back(mmi[Y][2]);
        } else {
            h.push_back(mmi[Y][0]);
            h.push_back(mmi[Y][1]);
        }
        sort(h.begin(),h.end());
        mi=min(mi,h[1]);

        if (mode==0) return ma;
        return max(ma,mi);
    }


    int cntX=dif, cntY=0;

    for (int i=17; i>=0; --i) {
        if (p[x][i]!=p[y][i]) {
            cntX+=(1<<i); cntY+=(1<<i);
            ma=max({ma,mmax[x][i],mmax[y][i]});
            x=p[x][i];
            y=p[y][i];
        }
    }
    LCA=p[x][0];
    ma=max({ma,mmax[x][0],mmax[y][0]});
    if (mode==0) return ma;

    --cntX; --cntY;
    int mi=min({mmax[LCA][0],lp[X],lp[Y]});
    if ((x==node[LCA][0] && y==node[LCA][1]) || (x==node[LCA][1] && y==node[LCA][0])) mi=min(mi,mmi[LCA][2]);
    else if (x==node[LCA][0] || y==node[LCA][0]) mi=min(mi,mmi[LCA][1]);
    else mi=min(mi,mmi[LCA][0]);

    mi=min({mi,mmi[X][1],mmi[Y][1]});

    x=X; y=Y;
    if (cntX>0) {
        for (int i=0; i<18; ++i) {
            if (cntX&(1<<i)) {
                mi=min(mi,mmin[x][i]);
                x=p[x][i];
            }
        }
    }
    if (cntY>0) {
        for (int i=0; i<18; ++i) {
            if (cntY&(1<<i)) {
                mi=min(mi,mmin[y][i]);
                y=p[y][i];
            }
        }
    }
    return max(ma,mi);
}

set<int> temp[100001];
void dfs3(int x, int par) {
    for (auto s : add[x]) temp[x].insert(s);

    for (auto s : adj[x]) {
        if (s.first==par) continue;
        dfs3(s.first,x);

        if (temp[s.first].size()>temp[x].size()) swap(temp[s.first],temp[x]);
        for (auto h : temp[s.first]) temp[x].insert(h);
    }

    if (temp[x].size()) lp[x]=*(temp[x].begin());
    else lp[x]=INT_MAX;

    for (auto s : del[x]) temp[x].erase(temp[x].find(s));
}


void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n=N;
    for (int i=0; i<M; ++i) edge.push_back({U[i],V[i],W[i]});
    sort(edge.begin(),edge.end());
    for (int i=0; i<n; ++i) pg[i]=i;
    for (auto s : edge) unite(s.u,s.v,s.w);

    mmax[0][0]=INT_MAX;
    dfs1(0,0);
    for (auto s : bridge) {
        mmin[s.u][0]=min(mmin[s.u][0],s.w);
        mmin[s.v][0]=min(mmin[s.v][0],s.w);
    }
    dfs2(0,0);

    //find loop
    for (auto s : bridge) {
        int ma=max(lca(s.u,s.v,0),s.w);
        add[s.u].push_back(ma);
        add[s.v].push_back(ma);
        del[LCA].push_back(ma);
    }
    dfs3(0,0);
}

int getMinimumFuelCapacity(int X, int Y) {
    int mx=lca(X,Y,1);
    if (mx==INT_MAX) return -1;
    else return mx;
}

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