Submission #869892

#	Time	Username	Problem	Language	Result	Execution time	Memory
869892		hgmhc	Swapping Cities (APIO20_swap)	C++17	100 / 100	394 ms	64700 KiB

swap

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define mup(x,y) x = min(x,y)
#define fi first
#define se second

const int N = 1e5+3;
vector<tuple<int,int,int>> edges;
vector<ii> group_log[N];
int swappable_moment[N];

int timer;
int deg[N];

struct dsu {
    set<int> s; int name; bool swappable;
    dsu(int i): s({i}), name(i), swappable(0) {}
    void insert(int x) {
        if (s.count(x)) swappable=1;
        else {
            s.insert(x);
            if (group_log[x].back().fi == timer) group_log[x].back().se = name;
            else group_log[x].emplace_back(timer, name);
        }
    }
} *ds[N];

dsu* merge(dsu* x, dsu* y) {
    if (x == y) {
        x->swappable = 1;
        mup(swappable_moment[x->name], timer);
        return x;
    }
    if (siz(x->s) < siz(y->s)) swap(x,y);
    x->swappable |= y->swappable;
    for (auto v : y->s) x->insert(v), ds[v] = x;
    if (x->swappable) mup(swappable_moment[x->name], timer);
    return x;
}

void init(int n, int m, vi u, vi v, vi w) {
    rep(i,0,m-1) edges.emplace_back(u[i],v[i],w[i]);
    sort(all(edges),[](auto&x, auto&y){ return get<2>(x) < get<2>(y); });
    rep(i,0,n-1) {
        ds[i] = new dsu(i);
        group_log[i].emplace_back(0,i);
        swappable_moment[i] = 1e9+1;
    }
    for (auto [u,v,w] : edges) {
        timer = w;
        if (++deg[u]>2) ds[u]->swappable=1;
        if (++deg[v]>2) ds[v]->swappable=1;
        ds[u] = ds[v] = merge(ds[u],ds[v]);
    }
}

int getMinimumFuelCapacity(int x, int y) {
    auto valid = [&](int t) {
        int a = prev(lower_bound(all(group_log[x]),ii{t+1,-1}))->se;
        int b = prev(lower_bound(all(group_log[y]),ii{t+1,-1}))->se;
        if (a != b) return false;
        return swappable_moment[a] <= t;
    };
    const int INF = 1e9+1;
    int a = 0, b = INF, m;
    while (a <= b) {
        m = (a+b)/2;
        if (valid(m)) b = m-1;
        else a = m+1;
    }
    if (a >= INF) return -1;
    return a;
}

#ifdef LOCAL

int main() {
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));
    
    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == scanf("%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);
    
    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        printf("%d\n", minimum_fuel_capacities[i]);
    }
    
    return 0;
}


#endif

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