Submission #571189

#	Time	Username	Problem	Language	Result	Execution time	Memory
571189		2fat2code	Swapping Cities (APIO20_swap)	C++17	50 / 100	294 ms	58196 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 300005;

int pardsu[nmax], last, lca[nmax][20], marked[nmax], grad[nmax], val[nmax], timp, in[nmax], out[nmax], apropiat[nmax], ans[nmax];
vector<pair<int, pair<int,int>>>edges;
vector<int>nod[nmax];

int findpar(int x){
    if(x != pardsu[x]){
        pardsu[x] = findpar(pardsu[x]);
    }
    return pardsu[x];
}

void dfs(int s, int apr, int par = 0){
    in[s] = ++timp;
    if(marked[s]) apr = val[s];
    ans[s] = apr;
    for(auto it : nod[s]){
        if(it != par){
            dfs(it, apr, s);
            ans[s] = min(ans[s], max(val[s], ans[it]));
        }
    }
    out[s] = ++timp;
}

bool is_lca(int x, int y){
    if(in[x] <= in[y] && out[x] >= out[y]) return true;
    else return false;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    last = N;
    for(int i=1;i<=N;i++) pardsu[i] = i;
    for(int i=0;i<M;i++){
        U[i]++; V[i]++;
        edges.push_back({W[i], {U[i], V[i]}});
    }
    sort(all(edges));
    for(auto it : edges){
        int x = findpar(it.sc.fr);
        int y = findpar(it.sc.sc);
        ++last;
        pardsu[y] = last;
        pardsu[x] = last;
        pardsu[last] = last;
        val[last] = it.fr;
        grad[it.sc.sc]++;
        grad[it.sc.fr]++;
        lca[x][0] = last;
        lca[y][0] = last;
        nod[last].push_back(x);
        if(x != y) nod[last].push_back(y);
        if(x == y){
            marked[last] = 1;
        }
        else{
            if(grad[it.sc.sc] >= 3 || grad[it.sc.fr] >= 3){
                marked[last] = 1;
            }
        }
    }
    for(int i=1;i<=19;i++){
        for(int j=1;j<=last;j++){
            lca[j][i] = lca[lca[j][i-1]][i-1];
        }
    }
    dfs(last, 1e9);
   // for(int i=1;i<=N+M;i++) cout << ans[i] << ' ';
//    cout << '\n';
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;
    int curr;
    if(is_lca(X, Y)) curr = X;
    else if(is_lca(Y, X)) curr = Y;
    else{
        curr = X;
        for(int i=19;i>=0;i--){
            if(lca[curr][i] != 0 && !is_lca(lca[curr][i], Y)) curr = lca[curr][i];
        }
        curr = lca[curr][0];
    }
    if(ans[curr] < 1e9){
        return ans[curr];
    }
    else{
        return -1;
    }
}


/**
6 5
0 1 1
1 2 2
1 3 3
1 4 4
4 5 5
3
0 4
5 4
0 2



*/

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