Submission #395219

#	Time	Username	Problem	Language	Result	Execution time	Memory
395219		syl123456	Swapping Cities (APIO20_swap)	C++17	100 / 100	267 ms	24360 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;

template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}

vector<pi> p, now;//pa, _t
vector<int> r, t;//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);
        t.push_back(inf);
    }
    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) {
            if (t[x] == inf)
                t[x] = i.first, mp[{x, t[x]}] = 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};
                t[x] = min(t[x], i.first);
                t[y] = min(t[y], i.first);
            }
            else
                now[x] = now[y] = pi(now[x].first ^ now[x].second ^ i.second.first, now[y].first ^ now[y].second ^ i.second.second);
            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;
    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;
    }
    while (p[X].first != X && t[X] == inf) X = p[X].first;
    return t[X] == inf ? -1 : max(ans, t[X]);
}

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