oj.uz

Submission #965018

# Submission time Handle Problem Language Result Execution time Memory
965018 2024-04-18T03:11:50 Z Pannda Swapping Cities (APIO20_swap) C++17
17 / 100
 2000 ms 524288 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> f;
    vector<int> siz;
    vector<int> deg;
    vector<int> ok;
    vector<vector<pair<int*, int>>> stk;

    DSU(int n) : f(n), siz(n, 1), deg(n, 0), ok(n, false) { iota(f.begin(), f.end(), 0); }

    int leader(int u) {
        while (u != f[u]) u = f[u];
        return u;
    }

    bool unionize(int u0, int v0) {
        stk.emplace_back();
        int u = leader(u0);
        int v = leader(v0);
        if (u == v) {
            stk.back().push_back({&ok[u], ok[u]}); ok[u] = true;
            return false;
        }
        if (siz[u] > siz[v]) swap(u, v);
        stk.back().push_back({&siz[v], siz[v]}); siz[v] += siz[u];
        stk.back().push_back({&deg[u0], deg[u0]}); deg[u0]++;
        stk.back().push_back({&deg[v0], deg[v0]}); deg[v0]++;
        stk.back().push_back({&ok[v], ok[v]}); if (deg[u0] >= 3 || deg[v0] >= 3) ok[v] = true; ok[v] = ok[v] | ok[u];
        stk.back().push_back({&f[u], f[u]}); f[u] = v;
        return true;
    }

    bool same(int u, int v) {
        return leader(u) == leader(v);
    }

    bool isOk(int u) {
        return ok[leader(u)];
    }

    void rollback() {
        for (auto [ptr, val] : stk.back()) {
            *ptr = val;
        }
        stk.pop_back();
    }
};
int n, m;
vector<array<int, 3>> edges;
const int B = 1600;
vector<DSU> dsus;
int b;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        edges[i] = {U[i], V[i], W[i]};
    }
    sort(edges.begin(), edges.end(), [&](array<int, 3> e0, array<int, 3> e1) { return e0[2] < e1[2]; });

    dsus.emplace_back(n);
    for (b = 0; B * b < m; b++) {
        dsus.push_back(dsus.back());
        for (int i = B * b; i < min(m, B * b + B); i++) {
            dsus.back().unionize(edges[i][0], edges[i][1]);
        }
    }
    b++;
}

int getMinimumFuelCapacity(int X, int Y) {
    if (!dsus.back().same(X, Y) || !dsus.back().isOk(X)) return -1;
    for (int b0 = 0; ; b0++) {
        if (dsus[b0 + 1].same(X, Y) && dsus[b0 + 1].isOk(X)) {
            int cnt = 0;
            int res;
            for (int i = B * b0; ; i++) {
                dsus[b0].unionize(edges[i][0], edges[i][1]);
                cnt++;
                if (dsus[b0].same(X, Y) && dsus[b0].isOk(X)) {
                    res = edges[i][2];
                    break;
                }
            }
            while (cnt--) dsus[b0].rollback();
            return res;
        }
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 262 ms 311960 KB Output is correct
10 Correct 412 ms 474400 KB Output is correct
11 Correct 349 ms 448252 KB Output is correct
12 Correct 404 ms 512788 KB Output is correct
13 Correct 391 ms 508644 KB Output is correct
14 Correct 251 ms 308228 KB Output is correct
15 Correct 414 ms 488700 KB Output is correct
16 Correct 418 ms 446896 KB Output is correct
17 Correct 460 ms 516072 KB Output is correct
18 Correct 442 ms 515572 KB Output is correct
19 Execution timed out 2090 ms 18440 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2062 ms 467728 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 1008 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 2 ms 704 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 2 ms 1112 KB Output is correct
26 Correct 3 ms 960 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 2 ms 860 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 262 ms 311960 KB Output is correct
11 Correct 412 ms 474400 KB Output is correct
12 Correct 349 ms 448252 KB Output is correct
13 Correct 404 ms 512788 KB Output is correct
14 Correct 391 ms 508644 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 1008 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 2 ms 704 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 2 ms 604 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 1112 KB Output is correct
31 Correct 3 ms 960 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 2 ms 860 KB Output is correct
34 Correct 13 ms 12316 KB Output is correct
35 Correct 395 ms 512708 KB Output is correct
36 Correct 383 ms 511184 KB Output is correct
37 Correct 379 ms 510496 KB Output is correct
38 Correct 404 ms 496964 KB Output is correct
39 Correct 369 ms 496000 KB Output is correct
40 Correct 335 ms 418376 KB Output is correct
41 Correct 400 ms 513512 KB Output is correct
42 Correct 443 ms 508140 KB Output is correct
43 Correct 487 ms 511656 KB Output is correct
44 Correct 416 ms 512832 KB Output is correct
45 Runtime error 380 ms 524288 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 262 ms 311960 KB Output is correct
10 Correct 412 ms 474400 KB Output is correct
11 Correct 349 ms 448252 KB Output is correct
12 Correct 404 ms 512788 KB Output is correct
13 Correct 391 ms 508644 KB Output is correct
14 Correct 251 ms 308228 KB Output is correct
15 Correct 414 ms 488700 KB Output is correct
16 Correct 418 ms 446896 KB Output is correct
17 Correct 460 ms 516072 KB Output is correct
18 Correct 442 ms 515572 KB Output is correct
19 Execution timed out 2062 ms 467728 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 262 ms 311960 KB Output is correct
11 Correct 412 ms 474400 KB Output is correct
12 Correct 349 ms 448252 KB Output is correct
13 Correct 404 ms 512788 KB Output is correct
14 Correct 391 ms 508644 KB Output is correct
15 Correct 251 ms 308228 KB Output is correct
16 Correct 414 ms 488700 KB Output is correct
17 Correct 418 ms 446896 KB Output is correct
18 Correct 460 ms 516072 KB Output is correct
19 Correct 442 ms 515572 KB Output is correct
20 Execution timed out 2062 ms 467728 KB Time limit exceeded
21 Halted 0 ms 0 KB -