Submission #1047347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047347		stdfloat	Swapping Cities (APIO20_swap)	C++17	0 / 100	0 ms	348 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
 
using ll = long long;
 
#define ff  first
#define ss  second
#define pii pair<int, int>
 
int aux;

vector<bool> swp;

vector<int> p, sz, cnt, w, h;

vector<vector<int>> sp;

vector<vector<int>> E;

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

void dfs(int x) {
    cout << "x " << x << '\n';
    for (auto i : E[x]) {
        h[i] = h[x] + 1;
        dfs(i);
    }
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> Wi) {
    aux = n;
    cnt.assign(n, 0);
    w.assign(n + m, 0);
    p.assign(n + m, 0);
    sz.assign(n + m, 1);
    E.assign(n + m, {});
    swp.assign(n + m, false);
    sp.assign(n + m, vector<int>(20, -1));

    iota(p.begin(), p.end(), 0);

    vector<pair<int, pii>> Ee;
    for (int i = 0; i < m; i++) {
        Ee.push_back({Wi[i], {U[i], V[i]}});
    }

    // cout << "asd" << endl;
    
    sort(Ee.begin(), Ee.end());
    for (auto i : Ee) {
        int x = fnd(i.ss.ff), y = fnd(i.ss.ss);

        // cout << x << ' ' << y << endl;

        cnt[i.ss.ff]++; cnt[i.ss.ss]++;

        // cout << 'a' << endl;

        E[aux].push_back(x);
        if (x != y) E[aux].push_back(y);

        // cout << 'a' << endl;

        p[x] = p[y] = sp[x][0] = sp[y][0] = aux;

        // cout << 'a' << endl;

        w[aux] = i.ff;
        // cout << 'a' << endl;
        swp[aux] = (x == y || swp[x] || swp[y] || max(cnt[i.ss.ff], cnt[i.ss.ss]) > 2);
        // cout << 'a' << endl;

        aux++;
    }

    // cout << "asd" << endl;

    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n + m; j++) {
            if (sp[j][i - 1] != -1) sp[j][i] = sp[sp[j][i - 1]][i - 1];
        }
    }

    // cout << 'a' << endl;

    h.assign(aux, 0);
    dfs(aux - 1);
}
 
int getMinimumFuelCapacity(int x, int y) {
    if (h[x] > h[y]) swap(x, y);

    // cout << "\nx " << x << ' ' << y << endl;

    for (int i = 19; i >= 0; i--) {
        if (h[x] <= h[y] - (1 << i)) y = sp[y][i];
    }

    // cout << x << ' ' << y << endl;

    for (int i = 19; i >= 0; i--) {
        if (sp[x][i] != sp[y][i]) {
            x = sp[x][i]; y = sp[y][i];
        }
    }

    x = sp[x][0];

    // cout << x << endl;

    if (swp[x]) return w[x];

    for (int i = 19; i >= 0; i--) {
        if (sp[x][i] != -1 && !swp[sp[x][i]]) x = sp[x][i];
    }

    return (sp[x][0] == -1 ? -1 : w[sp[x][0]]);
}

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