Submission #291386

#	Time	Username	Problem	Language	Result	Execution time	Memory
291386		muhammad_hokimiyon	Swapping Cities (APIO20_swap)	C++14	100 / 100	552 ms	87404 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long

int tim;
int p[300200];
int s[300200];
int su[300200];
int t1[300200];
int t2[300200];
int tin[300200];
int tout[300200];
int st;
int cnt[300200];
int up[300200][23];
int can[300200][23];
vector < int > v[300200];

int get2( int x )
{
    return (p[x] == x ? x : p[x] = get2(p[x]));
}

void merg( int x , int y , int w )
{
    cnt[x] += 1 , cnt[y] += 1;
    int px = get2( x );
    int py = get2( y );
    su[st] = w;
    if( cnt[x] >= 3 || cnt[y] >= 3 )t1[st] = 1;
    if( px == py ){
        v[st].push_back(px);
        t1[st] |= t1[px];
        t2[st] = t2[px] + 1;
        s[st] = s[px];
        p[px] = st;
    }else{
        t2[st] = t2[px] + t2[py] + 1;
        s[st] = s[px] + s[py];
        t1[st] |= (t1[px] | t1[py]);
        v[st].push_back(px);
        v[st].push_back(py);
        p[py] = st;
        p[px] = st;
    }
    st += 1;
}

void dfs( int x , int p )
{
    tin[x] = ++tim;
    up[x][0] = p;
    if( t2[x] >= s[x] ){
        t2[x] = 1;
    }else t2[x] = 0;
    can[x][0] = (t1[p] | t2[p]);
    for( int i = 1; i < 23; i++ ){
        up[x][i] = up[up[x][i - 1]][i - 1];
        can[x][i] = (can[x][i - 1] | can[up[x][i - 1]][i - 1]);
    }
    for( auto y : v[x] ){
        if( y == p )continue;
        dfs( y , x );
    }
    tout[x] = tim;
}

bool upper( int x , int y )
{
    return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
    st = N;
    vector < int > ord;
    for( int i = 0; i < M; i++ ){
        ord.push_back(i);
    }
    for( int i = 0; i < 300200; i++ ){
        p[i] = i;
        s[i] = 1;
    }
    sort( ord.begin() , ord.end() , [&](int i , int j){
        return W[i] < W[j];
    });
    for( int i = 0; i < M; i++ ){
        merg( U[ord[i]] , V[ord[i]] , W[ord[i]] );
    }
    st -= 1;
    dfs( st , st );
}

int get( int x , int y )
{
    if( upper( x , y ) )return x;
    if( upper( y , x ) )return y;
    for( int i = 22; i >= 0; i-- ){
        if( !upper( up[x][i] , y ) ){
            x = up[x][i];
        }
    }
    return up[x][0];
}

int get1( int x )
{
    for( int i = 22; i >= 0; i-- ){
        if( !can[x][i] ){
            x = up[x][i];
        }
    }
    return up[x][0];
}

int getMinimumFuelCapacity(int X, int Y)
{
    if( (t1[st] | t2[st]) == 0 ){
        return -1;
    }
    int f = get( X , Y );
    if( (t1[f] | t2[f]) ){
        return su[f];
    }else{
        return su[get1( f )];
    }
}

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