Submission #1064686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064686		sammyuri	Swapping Cities (APIO20_swap)	C++17	100 / 100	304 ms	39364 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
/*
a component becomes valid as soon as
there is either a loop or a node with degree 3+
if it is just a chain, clearly impossible
use persistent DSU and find for each node, the minimum time
until it is part of a valid component
*/
int n, m;
int curtime = 0;
const int MAXN = 1e5 + 5;
map<int, int> dsu[MAXN];
int sz[MAXN];
int mintime[MAXN];
bool good[MAXN];
int deg[MAXN];
vector<int> active_nodes[MAXN];
const int INF = 2e9;

int find(int node, int time) {
    auto it = dsu[node].upper_bound(time);
    it --;
    if ((*it).second == node) return node;
    return find((*it).second, time);
}


void init(int N, int M,
    std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N, m = M;
    curtime = 0;
    for (int i = 0; i < n; i ++) {
        mintime[i] = INF;
        dsu[i][0] = i;
        active_nodes[i].push_back(i);
        sz[i] = 1;
        deg[i] = 0; good[i] = false;
    }
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < M; i ++) {
        edges.push_back({W[i], {U[i], V[i]}});
    }
    sort(edges.begin(), edges.end());
    for (auto ee : edges) {
        int a = ee.second.first, b = ee.second.second;
        curtime = ee.first;
        bool madegood = false;
        // check if made good
        deg[a] ++; deg[b] ++;
        if (deg[a] >= 3 || deg[b] >= 3)
            madegood = true;
        a = find(a, curtime); b = find(b, curtime);
        if (a == b)
            madegood = true;
        // unite components
        if (a != b) {
            if (sz[a] > sz[b])
                swap(a, b);
            sz[b] += sz[a];
            for (auto aa : active_nodes[a])
                active_nodes[b].push_back(aa);
            active_nodes[a].clear();
            dsu[a][curtime] = b;
        }
        good[b] = good[b] | good[a] | madegood;
        if (good[b]) {
            for (auto aa : active_nodes[b])
                mintime[aa] = curtime;
            active_nodes[b].clear();
        }
    }
    // for (int i = 0; i < n; i ++)
    //     cout << mintime[i] << " "; cout << endl;
}

int getMinimumFuelCapacity(int X, int Y) {
    // lower bound
    int req = min(mintime[X], mintime[Y]);
    // find smallest time until they are in same component
    curtime = 1;
    while (X != Y) {
        auto itx = dsu[X].lower_bound(curtime),
        ity = dsu[Y].lower_bound(curtime);
        int nextmin = 2e9;
        if (itx != dsu[X].end() && X != (*itx).second)
            nextmin = min(nextmin, (*itx).first);
        if (ity != dsu[Y].end() && Y != (*ity).second)
            nextmin = min(nextmin, (*ity).first);
        // cout << X << " " << Y << " " << curtime << endl;
        // cout << nextmin << endl;
        curtime = nextmin;
        if (itx != dsu[X].end() && (*itx).first == curtime)
            X = (*itx).second;
        if (ity != dsu[Y].end() && (*ity).first == curtime)
            Y = (*ity).second;
    }
    int ans = max(req, curtime);
    if (ans == INF)
        return -1;
    return ans;
}

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