Submission #983595

#	Time	Username	Problem	Language	Result	Execution time	Memory
983595		RakhimovAmir	Swapping Cities (APIO20_swap)	C++17	0 / 100	142 ms	40240 KiB

swap

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

struct edge {
    int w, x, y;
};

const int N = 1e5 + 100, M = 30;
vector<pair<int, int>> g[N];
vector<edge> edges;
int prt[N], a[N], b[N], p[N][M], mx[N][M], tin[N], tout[N], tt, G;
bool fl[N], visited[N];
vector<int> v[N];

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

int findParent(int x) {\
    if (prt[x] == x)
        return x;
    return prt[x] = findParent(prt[x]);
}

void addEdge(int x, int y, int w) {
    g[x].push_back({w, y});
    g[y].push_back({w, x});
}

void merge(int x, int y, int w) {
    int X = prt[x], Y = prt[y];
    if (X == Y) {
        if (!fl[X])
            return;
        fl[X] = 0;
        G++;
        for (auto i : v[X]) {
            addEdge(G, i, w);
        }
        v[X].clear();
        v[X].push_back(G);
        return;
    }
    if (v[Y].size() > v[X].size()) {
        swap(x, y);
        swap(X, Y);
    }
    prt[Y] = X;
    for (auto i : v[Y]) {
        v[X].push_back(i);
    }
    if (!fl[X] || !fl[Y] || (x != a[X] && x != b[X]) || (y != a[Y] && y != b[Y])) {
        fl[X] = 0;
        fl[Y] = 0;
        G++;
        for (auto i : v[X]) {
            addEdge(G, i, w);
        }
        v[X].clear();
        v[X].push_back(G);
        return;
    } else {
        if (x == a[X]) {
            if (y == b[Y])
                a[X] = a[Y];
            else
                a[X] = b[Y];
        }
        else {
            if (y == b[Y])
                b[X] = a[Y];
            else
                b[X] = b[Y];
        }
    }
}

void dfs(int x, int par, int w) {
    tin[x] = ++tt;
    visited[x] = 1;
    for (auto to : g[x]) {
        if (!visited[to.second])
          dfs(to.second, x, to.first);
    }
    p[x][0] = par;
    mx[x][0] = w;
    for (int i = 1; i < M; i++) {
        p[x][i] = p[p[x][i - 1]][i - 1];
        mx[x][i] = max(mx[x][i - 1], mx[p[x][i - 1]][i - 1]);
        // cout << mx[x][i] << " " << x << " " << i << "\n";
    }
    tout[x] = tt;
}

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

int lca(int x, int y) {
    if (ispr(x, y))
        return x;
    if (ispr(y, x))
        return y;
    for (int i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y))
            x = p[x][i];
    }
    x = p[x][0];
    return x;
}

int findMax(int x, int y) {
    int ret = 0;
    if (x == y)
        return 0;
     for (int i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y)) {
            ret = max(ret, mx[x][i]);
            x = p[x][i];
        }
    }
    ret = max(ret, mx[x][0]);
    return ret;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < N; i++) {
        prt[i] = i;
        a[i] = i;
        b[i] = i;
        fl[i] = 1;
        v[i].push_back(i);
    }
    G = N - 1;
    for (int i = 0; i < M; i++) {
        edges.push_back({W[i], U[i], V[i]});
    }
    sort(edges.begin(), edges.end(), cmp);
    for (auto i : edges) {
        merge(i.x, i.y, i.w);
    }

    for (int i = 0; i <= G; i++) {
        // int pr = findParent(i);
        if (!visited[i]) {
            dfs(i, i, 0);
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int P = lca(X, Y);
    if (!ispr(P, X) || !ispr(P, Y) || X == Y)
      return -1;
    return max(findMax(X, P), findMax(Y, P));
}

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