oj.uz

Submission #869873

# Submission time Handle Problem Language Result Execution time Memory
869873 2023-11-06T03:25:52 Z hgmhc Swapping Cities (APIO20_swap) C++17
7 / 100
 223 ms 32560 KB 
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; 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
#define dbg(...) fprintf(stderr,__VA_ARGS__)

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 (siz(x->s) < siz(y->s)) swap(x,y);
    x->swappable |= y->swappable;
    for (auto v : y->s) x->insert(v);
    if (x->swappable) mup(swappable_moment[x->name], timer);
    y = 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),[](const auto&x, const auto&y){ return get<2>(x) < get<2>(y); });
    rep(i,0,n-1) ds[i] = new dsu(i);
    rep(i,0,n-1) {
        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]);
    }
    
    // rep(i,0,n-1) {
    //     printf("group log of %d: ", i);
    //     for (auto [t,g] : group_log[i]) {
    //         printf("(%d,%d) ", t,g);
    //     }
    //     puts("");
    // }
    // rep(i,0,n-1) {
    //     printf("swappable log of %d: ", i);
    //     for (auto [t,s] : swapp_log[i]) {
    //         printf("(%d,%d) ", t,s);
    //     }
    //     puts("");
    // }
}

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 67 ms 24776 KB Output is correct
10 Correct 124 ms 29688 KB Output is correct
11 Correct 89 ms 29124 KB Output is correct
12 Correct 98 ms 30664 KB Output is correct
13 Correct 99 ms 27080 KB Output is correct
14 Correct 76 ms 25032 KB Output is correct
15 Correct 191 ms 31456 KB Output is correct
16 Correct 215 ms 31092 KB Output is correct
17 Correct 189 ms 32560 KB Output is correct
18 Correct 214 ms 31164 KB Output is correct
19 Incorrect 84 ms 10600 KB Output isn't correct
20 Halted 0 ms 0 KB -

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 4188 KB Output is correct
3 Correct 198 ms 28264 KB Output is correct
4 Correct 211 ms 29388 KB Output is correct
5 Correct 201 ms 28764 KB Output is correct
6 Correct 203 ms 29112 KB Output is correct
7 Correct 208 ms 29108 KB Output is correct
8 Correct 209 ms 28096 KB Output is correct
9 Correct 223 ms 28996 KB Output is correct
10 Correct 198 ms 28060 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 4188 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 1 ms 3928 KB Output is correct
10 Incorrect 2 ms 4440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4188 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 67 ms 24776 KB Output is correct
11 Correct 124 ms 29688 KB Output is correct
12 Correct 89 ms 29124 KB Output is correct
13 Correct 98 ms 30664 KB Output is correct
14 Correct 99 ms 27080 KB Output is correct
15 Incorrect 2 ms 4440 KB Output isn't correct
16 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 4188 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 67 ms 24776 KB Output is correct
10 Correct 124 ms 29688 KB Output is correct
11 Correct 89 ms 29124 KB Output is correct
12 Correct 98 ms 30664 KB Output is correct
13 Correct 99 ms 27080 KB Output is correct
14 Correct 76 ms 25032 KB Output is correct
15 Correct 191 ms 31456 KB Output is correct
16 Correct 215 ms 31092 KB Output is correct
17 Correct 189 ms 32560 KB Output is correct
18 Correct 214 ms 31164 KB Output is correct
19 Correct 198 ms 28264 KB Output is correct
20 Correct 211 ms 29388 KB Output is correct
21 Correct 201 ms 28764 KB Output is correct
22 Correct 203 ms 29112 KB Output is correct
23 Correct 208 ms 29108 KB Output is correct
24 Correct 209 ms 28096 KB Output is correct
25 Correct 223 ms 28996 KB Output is correct
26 Correct 198 ms 28060 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 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4188 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 67 ms 24776 KB Output is correct
11 Correct 124 ms 29688 KB Output is correct
12 Correct 89 ms 29124 KB Output is correct
13 Correct 98 ms 30664 KB Output is correct
14 Correct 99 ms 27080 KB Output is correct
15 Correct 76 ms 25032 KB Output is correct
16 Correct 191 ms 31456 KB Output is correct
17 Correct 215 ms 31092 KB Output is correct
18 Correct 189 ms 32560 KB Output is correct
19 Correct 214 ms 31164 KB Output is correct
20 Correct 198 ms 28264 KB Output is correct
21 Correct 211 ms 29388 KB Output is correct
22 Correct 201 ms 28764 KB Output is correct
23 Correct 203 ms 29112 KB Output is correct
24 Correct 208 ms 29108 KB Output is correct
25 Correct 209 ms 28096 KB Output is correct
26 Correct 223 ms 28996 KB Output is correct
27 Correct 198 ms 28060 KB Output is correct
28 Incorrect 2 ms 4440 KB Output isn't correct
29 Halted 0 ms 0 KB -