Submission #393409

#	Time	Username	Problem	Language	Result	Execution time	Memory
393409		BartolM	Swapping Cities (APIO20_swap)	C++17	100 / 100	389 ms	45876 KiB

swap

#include "swap.h"
#define DEBUG 0
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=3e5+50;
const int LOG=18;

int n, m, uk;
vector <pip> v;
vector <int> ls[N];
int P[N], lanac[N], deg[N], dep[N];
int cnt[N][4], par[LOG+1][N];

int name(int x) {
    if (x==P[x]) return x;
    P[x]=name(P[x]);
    return P[x];
}

void check(int x, int val) {
    if (lanac[x]!=INF) return;
    if (cnt[x][3]) lanac[x]=val;
    else if (!cnt[x][1] && cnt[x][2]) lanac[x]=val;
    #if DEBUG
        if (lanac[x]!=INF) printf("%d ima lanac %d\n", x, val);
    #endif // DEBUG
}

void pov_deg(int x, int val) {
    if (deg[x]>=3) return;
    int y=name(x);
    cnt[y][deg[x]]--; deg[x]++; cnt[y][deg[x]]++;
    check(y, val);
}

void dfs(int node, int papi) {
    dep[node]=dep[papi]+1;
    par[0][node]=papi;
    lanac[node]=min(lanac[node], lanac[papi]);
    for (int sus:ls[node]) dfs(sus, node);
}

void build() {
    for (int i=1; i<=LOG; ++i) {
        for (int j=0; j<uk; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=LOG; i>=0; --i) {
        if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
    }
    if (x==y) return x;
    for (int i=LOG; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

void init(int NN, int MM, vector<int> U, vector<int> V, vector<int> W) {
    n=NN, m=MM;
    for (int i=0; i<m; ++i) v.pb(mp(W[i], mp(U[i], V[i])));
    sort(v.begin(), v.end());

    for (int i=0; i<2*n; ++i) P[i]=i;
    for (int i=0; i<n; ++i) cnt[i][0]=1;
    memset(lanac, INF, sizeof lanac);
    uk=n;

    for (pip pp:v) {
        #if DEBUG
            printf("edge: (%d <-> %d) %d\n", pp.Y.X, pp.Y.Y, pp.X);
        #endif
        int x=name(pp.Y.X), y=name(pp.Y.Y);
        int curr=x;
        if (x!=y) {
            curr=uk++;
            P[y]=P[x]=curr;

            #if DEBUG
                printf("parent od %d i %d je %d\n", x, y, curr);
            #endif // DEBUG

            ls[curr].pb(x); ls[curr].pb(y);
            for (int i=0; i<4; ++i) cnt[curr][i]=cnt[x][i]+cnt[y][i];
            lanac[curr]=min(lanac[x], lanac[y]);
            lanac[curr]=max(lanac[curr], pp.X);
        }
        pov_deg(pp.Y.X, pp.X); pov_deg(pp.Y.Y, pp.X);
        #if DEBUG
            printf("\n");
        #endif // DEBUG
    }
    #if DEBUG
        for (int i=0; i<uk; ++i) printf("node: %d, lanac: %d\n", i, lanac[i]);
    #endif
    dfs(name(0), name(0));
    build();
}

int getMinimumFuelCapacity(int x, int y) {
    int lc=lca(x, y);
    return lanac[lc]==INF ? -1 : lanac[lc];
}

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