Submission #474278

#	Time	Username	Problem	Language	Result	Execution time	Memory
474278		JovanB	Swapping Cities (APIO20_swap)	C++17	100 / 100	495 ms	47920 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 100000;
const int LOG = 17;
const int INF = 1000000007;

int val[N+5][LOG+1];
int par[N+5][LOG+1];

vector <pair <int, int>> graf[N+5];

int tjm;
int in[N+5], out[N+5];

void dfs(int v, int p, int d){
    in[v] = ++tjm;
    par[v][0] = p;
    val[v][0] = d;
    for(int j=1; j<=LOG; j++){
        par[v][j] = par[par[v][j-1]][j-1];
        val[v][j] = max(val[v][j-1], val[par[v][j-1]][j-1]);
    }
    for(auto pr : graf[v]) if(pr.first != p) dfs(pr.first, v, pr.second);
    out[v] = tjm;
}

int moze[N+5];
int deg[N+5];
vector <int> vec[N+5];
int comp[N+5];
bool ima[N+5];

void init(int n, int m, vector <int> U, vector <int> V, vector <int> W) {
    for(int i=1; i<=n; i++) moze[i] = INF, comp[i] = i, vec[i].push_back(i);
    vector <tuple <int, int, int>> edges;
    for(int i=0; i<m; i++){
        int a = U[i] + 1;
        int b = V[i] + 1;
        int c = W[i];
        edges.push_back({c, a, b});
    }
    sort(edges.begin(), edges.end());
    for(auto e : edges){
        int c, a, b;
        tie(c, a, b) = e;
        if(comp[a] == comp[b]){
            if(ima[comp[a]]) continue;
            ima[comp[a]] = 1;
            for(auto x : vec[comp[a]]) moze[x] = c;
            continue;
        }
        graf[a].push_back({b, c});
        graf[b].push_back({a, c});
        bool novi = 0;
        deg[a]++;
        deg[b]++;
        if(deg[a] >= 3 || deg[b] >= 3) novi = 1;
        a = comp[a];
        b = comp[b];
        if(vec[a].size() < vec[b].size()) swap(a, b);
        if(!ima[a] && (novi || ima[b])){
            ima[a] = 1;
            for(auto x : vec[a]) moze[x] = c;
        }
        if(!ima[b] && (novi || ima[a])){
            ima[b] = 1;
            for(auto x : vec[b]) moze[x] = c;
        }
        for(auto x : vec[b]) comp[x] = a, vec[a].push_back(x);
        vec[b].clear();
    }
    dfs(1, 0, 0);
}

bool is_parent(int a, int b){ return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]); }

int query(int x, int y){
    int res = 0;
    for(int j=LOG; j>=0; j--) if(!is_parent(par[x][j], y)) res = max(res, val[x][j]), x = par[x][j];
    if(!is_parent(x, y)) res = max(res, val[x][0]);
    for(int j=LOG; j>=0; j--) if(!is_parent(par[y][j], x)) res = max(res, val[y][j]), y = par[y][j];
    if(!is_parent(y, x)) res = max(res, val[y][0]);
    return res;
}

int getMinimumFuelCapacity(int x, int y) {
    x++;
    y++;
    int g = max(query(x, y), moze[x]);
    return (g == INF ? -1 : g);
}

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