Submission #395212

#	Time	Username	Problem	Language	Result	Execution time	Memory
395212		syl123456	Swapping Cities (APIO20_swap)	C++17	0 / 100	1 ms	204 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
typedef pair<int, int> pi;
typedef pair<int, pi> pp;
const int inf = 1 << 30;
vector<pi> p, now;//pa, _t
vector<int> r;//rank
map<pi, pi> mp;//[ver, _t] : [l, r]

int find(int i) {
    return p[i].first == i ? i : find(p[i].first);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    p.clear(), now.clear(), r.clear(), mp.clear();
    for (int i = 0; i < N; ++i) {
        p.emplace_back(i, inf);
        now.emplace_back(i, i);
        r.push_back(0);
    }
    vector<pp> e;
    for (int i = 0; i < M; ++i) e.emplace_back(W[i], pi(U[i], V[i]));
    sort(all(e));
    for (pp i : e) {
        int x = find(i.second.first), y = find(i.second.second);
        if (x == y) mp[{x, i.first}] = now[x] = {-1, -1};
        else {
            if ((i.second.first != now[x].first && i.second.first != now[x].second) || (i.second.second != now[y].first && i.second.second != now[y].second))
                now[x] = now[y] = {-1, -1};
            if (r[x] < r[y]) swap(x, y);
            else if (r[x] == r[y]) ++r[x];
            p[y] = {x, i.first};
            mp[{x, i.first}] = now[x];
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans = 0, x = X, y = Y;
    while (X != Y) {
        ans = min(p[X].second, p[Y].second);
        while (p[X].second <= ans) X = p[X].first;
        while (p[Y].second <= ans) Y = p[Y].first;
    }
    pi tmp = mp[{X, ans}];
    if (tmp == pi(x, y) || tmp == pi(y, x)) {
        auto it = mp.upper_bound({X, ans});
        if (it != mp.end() && it->second.first == X) {
            return it->first.second;
        }
        return p[X].second;
    }
    return ans;
}

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