oj.uz

Submission #869879

# Submission time Handle Problem Language Result Execution time Memory
869879 2023-11-06T05:27:08 Z hgmhc Swapping Cities (APIO20_swap) C++17
13 / 100
 384 ms 61420 KB 
#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 per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#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];

void merge(dsu* &x, dsu* &y) {
    if (x == y) {
        x->swappable = 1;
        mup(swappable_moment[x->name], timer);
        return;
    }
    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);
}

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;
        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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 156 ms 46512 KB Output is correct
10 Correct 202 ms 55240 KB Output is correct
11 Correct 197 ms 54004 KB Output is correct
12 Correct 221 ms 57548 KB Output is correct
13 Correct 113 ms 31432 KB Output is correct
14 Correct 175 ms 46020 KB Output is correct
15 Correct 365 ms 58544 KB Output is correct
16 Correct 357 ms 56388 KB Output is correct
17 Correct 365 ms 60204 KB Output is correct
18 Correct 224 ms 32988 KB Output is correct
19 Correct 125 ms 15204 KB Output is correct
20 Correct 374 ms 59564 KB Output is correct
21 Correct 364 ms 57732 KB Output is correct
22 Correct 384 ms 61420 KB Output is correct
23 Correct 228 ms 34328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 213 ms 28392 KB Output is correct
4 Correct 214 ms 29412 KB Output is correct
5 Correct 209 ms 28764 KB Output is correct
6 Correct 219 ms 29420 KB Output is correct
7 Correct 213 ms 29248 KB Output is correct
8 Correct 208 ms 28328 KB Output is correct
9 Correct 216 ms 29004 KB Output is correct
10 Correct 207 ms 28032 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Incorrect 1 ms 3928 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 156 ms 46512 KB Output is correct
10 Correct 202 ms 55240 KB Output is correct
11 Correct 197 ms 54004 KB Output is correct
12 Correct 221 ms 57548 KB Output is correct
13 Correct 113 ms 31432 KB Output is correct
14 Correct 175 ms 46020 KB Output is correct
15 Correct 365 ms 58544 KB Output is correct
16 Correct 357 ms 56388 KB Output is correct
17 Correct 365 ms 60204 KB Output is correct
18 Correct 224 ms 32988 KB Output is correct
19 Correct 213 ms 28392 KB Output is correct
20 Correct 214 ms 29412 KB Output is correct
21 Correct 209 ms 28764 KB Output is correct
22 Correct 219 ms 29420 KB Output is correct
23 Correct 213 ms 29248 KB Output is correct
24 Correct 208 ms 28328 KB Output is correct
25 Correct 216 ms 29004 KB Output is correct
26 Correct 207 ms 28032 KB Output is correct
27 Incorrect 2 ms 4440 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -