oj.uz

Submission #674139

# Submission time Handle Problem Language Result Execution time Memory
674139 2022-12-23T10:05:49 Z ghostwriter Swapping Cities (APIO20_swap) C++17
100 / 100
 533 ms 49020 KB 
#include "swap.h"

#include <vector>

// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    #include <debug.h>
    #include "grader.cpp"
#else
    #define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { T d2 = (a | b) & -(a | b); a /= d2; b /= d2; WHILE(b) { a = a % b; swap(a, b); } return a * d2; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
void _assert(bool statement) { if (statement) return; cerr << "\n>> Assertion failed!\n"; exit(0); }
void _assert(bool statement, const str &message) { if (statement) return; cerr << "\n>> Assertion failed: " << message << '\n'; exit(0); }
void _error(const str &message) { cerr << "\n>> Error: " << message << '\n'; exit(0); }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    GOAT
----------------------------------------------------------------
*/
struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator <(const Edge &b) { return w < b.w; }
};
struct Status {
    int time, cnt[4];
    Status() { time = 0; memset(cnt, 0, sizeof cnt); }
};
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
int edgenum, p[MAXN], w1[MAXN], cpos[MAXN], d[MAXN];
Status csta[MAXN];
Edge e[MAXM];
vi vt[MAXN];
vpi pos[MAXN];
vector<Status> sta[MAXN];
void join(int u, int v, int w) {
    int un = cpos[u], vn = cpos[v];
    if (sz(vt[un]) < sz(vt[vn])) {
        swap(u, v);
        swap(un, vn);
    }
    if (un != vn) {
        EACH(i, vt[vn]) {
            vt[un].pb(i);
            pos[i].pb({w, un});
            cpos[i] = un;
        }
        FRN(i, 4) csta[un].cnt[i] += csta[vn].cnt[i];
    }
    --csta[un].cnt[min(d[u], 3)];
    --csta[un].cnt[min(d[v], 3)];
    ++d[u];
    ++d[v];
    ++csta[un].cnt[min(d[u], 3)];
    ++csta[un].cnt[min(d[v], 3)];
    sta[un].pb(Status());
    sta[un].bk().time = w;
    FRN(i, 4) sta[un].bk().cnt[i] = csta[un].cnt[i];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    edgenum = M;
    FRN(i, M) w1[i] = W[i];
    sort(w1, w1 + M);
    w1[M] = -1;
    FRN(i, M) {
        W[i] = lb(w1, w1 + M, W[i]) - w1;
        e[i] = Edge(U[i], V[i], W[i]);
    }
    sort(e, e + M);
    FRN(i, N) {
        vt[i].pb(i);
        pos[i].pb({0, i});
        cpos[i] = i;
        csta[i].cnt[0] = 1;
    }
    FRN(i, M) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        join(u, v, w);
    }
}
int getp(int u, int time) {
    int l = 0, r = sz(pos[u]) - 1, ans = -1;
    WHILE(l <= r) {
        int mid = l + (r - l) / 2;
        if (pos[u][mid].st <= time) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return pos[u][ans].nd;
}
Status gets(int u, int time) {
    int l = 0, r = sz(sta[u]) - 1, ans = -1;
    WHILE(l <= r) {
        int mid = l + (r - l) / 2;
        if (sta[u][mid].time <= time) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return sta[u][ans];
}
bool check(int X, int Y, int time) {
    int px = getp(X, time), py = getp(Y, time);
    if (px != py) return 0;
    Status cur = gets(px, time);
    if (cur.cnt[3]) return 1;
    int total = 0; FRN(i, 4) total += cur.cnt[i];
    if (cur.cnt[2] == total - 2) return 0;
    return 1;
}
int getMinimumFuelCapacity(int X, int Y) {
    int l = 0, r = edgenum - 1, ans = edgenum;
    WHILE(l <= r) {
        int mid = l + (r - l) / 2;
        if (check(X, Y, mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return w1[ans];
}
/*
3 2
0 1 5
0 2 5
1
1 2
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 5 ms 9300 KB Output is correct
3 Correct 5 ms 9300 KB Output is correct
4 Correct 6 ms 9324 KB Output is correct
5 Correct 6 ms 9428 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 6 ms 9516 KB Output is correct
8 Correct 6 ms 9556 KB Output is correct
9 Correct 167 ms 30224 KB Output is correct
10 Correct 216 ms 34652 KB Output is correct
11 Correct 201 ms 34096 KB Output is correct
12 Correct 213 ms 35692 KB Output is correct
13 Correct 132 ms 27204 KB Output is correct
14 Correct 169 ms 30468 KB Output is correct
15 Correct 402 ms 39388 KB Output is correct
16 Correct 374 ms 38388 KB Output is correct
17 Correct 441 ms 40124 KB Output is correct
18 Correct 297 ms 31424 KB Output is correct
19 Correct 143 ms 18476 KB Output is correct
20 Correct 384 ms 40176 KB Output is correct
21 Correct 413 ms 39616 KB Output is correct
22 Correct 387 ms 41384 KB Output is correct
23 Correct 327 ms 32844 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 5 ms 9300 KB Output is correct
3 Correct 424 ms 29232 KB Output is correct
4 Correct 405 ms 29764 KB Output is correct
5 Correct 401 ms 29736 KB Output is correct
6 Correct 426 ms 29640 KB Output is correct
7 Correct 372 ms 29876 KB Output is correct
8 Correct 413 ms 29248 KB Output is correct
9 Correct 359 ms 29552 KB Output is correct
10 Correct 366 ms 29160 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 5 ms 9300 KB Output is correct
3 Correct 5 ms 9300 KB Output is correct
4 Correct 6 ms 9324 KB Output is correct
5 Correct 6 ms 9428 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 6 ms 9516 KB Output is correct
8 Correct 6 ms 9556 KB Output is correct
9 Correct 5 ms 9300 KB Output is correct
10 Correct 7 ms 9464 KB Output is correct
11 Correct 6 ms 9556 KB Output is correct
12 Correct 6 ms 9432 KB Output is correct
13 Correct 6 ms 9428 KB Output is correct
14 Correct 8 ms 9404 KB Output is correct
15 Correct 6 ms 9464 KB Output is correct
16 Correct 5 ms 9556 KB Output is correct
17 Correct 6 ms 9460 KB Output is correct
18 Correct 6 ms 9428 KB Output is correct
19 Correct 5 ms 9428 KB Output is correct
20 Correct 6 ms 9508 KB Output is correct
21 Correct 7 ms 9428 KB Output is correct
22 Correct 9 ms 9468 KB Output is correct
23 Correct 6 ms 9428 KB Output is correct
24 Correct 7 ms 9592 KB Output is correct
25 Correct 8 ms 9592 KB Output is correct
26 Correct 6 ms 9632 KB Output is correct
27 Correct 6 ms 9452 KB Output is correct
28 Correct 6 ms 9556 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 5 ms 9300 KB Output is correct
3 Correct 5 ms 9300 KB Output is correct
4 Correct 5 ms 9300 KB Output is correct
5 Correct 6 ms 9324 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 6 ms 9428 KB Output is correct
8 Correct 6 ms 9516 KB Output is correct
9 Correct 6 ms 9556 KB Output is correct
10 Correct 167 ms 30224 KB Output is correct
11 Correct 216 ms 34652 KB Output is correct
12 Correct 201 ms 34096 KB Output is correct
13 Correct 213 ms 35692 KB Output is correct
14 Correct 132 ms 27204 KB Output is correct
15 Correct 7 ms 9464 KB Output is correct
16 Correct 6 ms 9556 KB Output is correct
17 Correct 6 ms 9432 KB Output is correct
18 Correct 6 ms 9428 KB Output is correct
19 Correct 8 ms 9404 KB Output is correct
20 Correct 6 ms 9464 KB Output is correct
21 Correct 5 ms 9556 KB Output is correct
22 Correct 6 ms 9460 KB Output is correct
23 Correct 6 ms 9428 KB Output is correct
24 Correct 5 ms 9428 KB Output is correct
25 Correct 6 ms 9508 KB Output is correct
26 Correct 7 ms 9428 KB Output is correct
27 Correct 9 ms 9468 KB Output is correct
28 Correct 6 ms 9428 KB Output is correct
29 Correct 7 ms 9592 KB Output is correct
30 Correct 8 ms 9592 KB Output is correct
31 Correct 6 ms 9632 KB Output is correct
32 Correct 6 ms 9452 KB Output is correct
33 Correct 6 ms 9556 KB Output is correct
34 Correct 22 ms 12380 KB Output is correct
35 Correct 233 ms 35280 KB Output is correct
36 Correct 242 ms 34912 KB Output is correct
37 Correct 220 ms 34620 KB Output is correct
38 Correct 242 ms 33624 KB Output is correct
39 Correct 213 ms 33204 KB Output is correct
40 Correct 191 ms 30684 KB Output is correct
41 Correct 258 ms 36036 KB Output is correct
42 Correct 229 ms 35876 KB Output is correct
43 Correct 133 ms 26400 KB Output is correct
44 Correct 212 ms 33376 KB Output is correct
45 Correct 155 ms 30552 KB Output is correct
46 Correct 215 ms 35048 KB Output is correct
47 Correct 200 ms 31452 KB Output is correct
48 Correct 158 ms 29316 KB Output is correct
49 Correct 98 ms 23648 KB Output is correct
50 Correct 85 ms 19944 KB Output is correct
51 Correct 144 ms 27564 KB Output is correct
52 Correct 248 ms 39792 KB Output is correct
53 Correct 231 ms 37024 KB Output is correct
54 Correct 292 ms 44676 KB Output is correct
55 Correct 123 ms 26440 KB Output is correct
56 Correct 200 ms 34892 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 5 ms 9300 KB Output is correct
3 Correct 5 ms 9300 KB Output is correct
4 Correct 6 ms 9324 KB Output is correct
5 Correct 6 ms 9428 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 6 ms 9516 KB Output is correct
8 Correct 6 ms 9556 KB Output is correct
9 Correct 167 ms 30224 KB Output is correct
10 Correct 216 ms 34652 KB Output is correct
11 Correct 201 ms 34096 KB Output is correct
12 Correct 213 ms 35692 KB Output is correct
13 Correct 132 ms 27204 KB Output is correct
14 Correct 169 ms 30468 KB Output is correct
15 Correct 402 ms 39388 KB Output is correct
16 Correct 374 ms 38388 KB Output is correct
17 Correct 441 ms 40124 KB Output is correct
18 Correct 297 ms 31424 KB Output is correct
19 Correct 424 ms 29232 KB Output is correct
20 Correct 405 ms 29764 KB Output is correct
21 Correct 401 ms 29736 KB Output is correct
22 Correct 426 ms 29640 KB Output is correct
23 Correct 372 ms 29876 KB Output is correct
24 Correct 413 ms 29248 KB Output is correct
25 Correct 359 ms 29552 KB Output is correct
26 Correct 366 ms 29160 KB Output is correct
27 Correct 7 ms 9464 KB Output is correct
28 Correct 6 ms 9556 KB Output is correct
29 Correct 6 ms 9432 KB Output is correct
30 Correct 6 ms 9428 KB Output is correct
31 Correct 8 ms 9404 KB Output is correct
32 Correct 6 ms 9464 KB Output is correct
33 Correct 5 ms 9556 KB Output is correct
34 Correct 6 ms 9460 KB Output is correct
35 Correct 6 ms 9428 KB Output is correct
36 Correct 22 ms 12380 KB Output is correct
37 Correct 233 ms 35280 KB Output is correct
38 Correct 242 ms 34912 KB Output is correct
39 Correct 220 ms 34620 KB Output is correct
40 Correct 242 ms 33624 KB Output is correct
41 Correct 213 ms 33204 KB Output is correct
42 Correct 191 ms 30684 KB Output is correct
43 Correct 258 ms 36036 KB Output is correct
44 Correct 229 ms 35876 KB Output is correct
45 Correct 133 ms 26400 KB Output is correct
46 Correct 212 ms 33376 KB Output is correct
47 Correct 33 ms 12764 KB Output is correct
48 Correct 436 ms 40268 KB Output is correct
49 Correct 416 ms 39744 KB Output is correct
50 Correct 431 ms 39528 KB Output is correct
51 Correct 410 ms 38948 KB Output is correct
52 Correct 389 ms 37152 KB Output is correct
53 Correct 331 ms 30676 KB Output is correct
54 Correct 409 ms 40924 KB Output is correct
55 Correct 404 ms 40880 KB Output is correct
56 Correct 360 ms 31792 KB Output is correct
57 Correct 376 ms 38356 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 5 ms 9300 KB Output is correct
3 Correct 5 ms 9300 KB Output is correct
4 Correct 5 ms 9300 KB Output is correct
5 Correct 6 ms 9324 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 6 ms 9428 KB Output is correct
8 Correct 6 ms 9516 KB Output is correct
9 Correct 6 ms 9556 KB Output is correct
10 Correct 167 ms 30224 KB Output is correct
11 Correct 216 ms 34652 KB Output is correct
12 Correct 201 ms 34096 KB Output is correct
13 Correct 213 ms 35692 KB Output is correct
14 Correct 132 ms 27204 KB Output is correct
15 Correct 169 ms 30468 KB Output is correct
16 Correct 402 ms 39388 KB Output is correct
17 Correct 374 ms 38388 KB Output is correct
18 Correct 441 ms 40124 KB Output is correct
19 Correct 297 ms 31424 KB Output is correct
20 Correct 424 ms 29232 KB Output is correct
21 Correct 405 ms 29764 KB Output is correct
22 Correct 401 ms 29736 KB Output is correct
23 Correct 426 ms 29640 KB Output is correct
24 Correct 372 ms 29876 KB Output is correct
25 Correct 413 ms 29248 KB Output is correct
26 Correct 359 ms 29552 KB Output is correct
27 Correct 366 ms 29160 KB Output is correct
28 Correct 7 ms 9464 KB Output is correct
29 Correct 6 ms 9556 KB Output is correct
30 Correct 6 ms 9432 KB Output is correct
31 Correct 6 ms 9428 KB Output is correct
32 Correct 8 ms 9404 KB Output is correct
33 Correct 6 ms 9464 KB Output is correct
34 Correct 5 ms 9556 KB Output is correct
35 Correct 6 ms 9460 KB Output is correct
36 Correct 6 ms 9428 KB Output is correct
37 Correct 22 ms 12380 KB Output is correct
38 Correct 233 ms 35280 KB Output is correct
39 Correct 242 ms 34912 KB Output is correct
40 Correct 220 ms 34620 KB Output is correct
41 Correct 242 ms 33624 KB Output is correct
42 Correct 213 ms 33204 KB Output is correct
43 Correct 191 ms 30684 KB Output is correct
44 Correct 258 ms 36036 KB Output is correct
45 Correct 229 ms 35876 KB Output is correct
46 Correct 133 ms 26400 KB Output is correct
47 Correct 212 ms 33376 KB Output is correct
48 Correct 33 ms 12764 KB Output is correct
49 Correct 436 ms 40268 KB Output is correct
50 Correct 416 ms 39744 KB Output is correct
51 Correct 431 ms 39528 KB Output is correct
52 Correct 410 ms 38948 KB Output is correct
53 Correct 389 ms 37152 KB Output is correct
54 Correct 331 ms 30676 KB Output is correct
55 Correct 409 ms 40924 KB Output is correct
56 Correct 404 ms 40880 KB Output is correct
57 Correct 360 ms 31792 KB Output is correct
58 Correct 376 ms 38356 KB Output is correct
59 Correct 143 ms 18476 KB Output is correct
60 Correct 384 ms 40176 KB Output is correct
61 Correct 413 ms 39616 KB Output is correct
62 Correct 387 ms 41384 KB Output is correct
63 Correct 327 ms 32844 KB Output is correct
64 Correct 5 ms 9428 KB Output is correct
65 Correct 6 ms 9508 KB Output is correct
66 Correct 7 ms 9428 KB Output is correct
67 Correct 9 ms 9468 KB Output is correct
68 Correct 6 ms 9428 KB Output is correct
69 Correct 7 ms 9592 KB Output is correct
70 Correct 8 ms 9592 KB Output is correct
71 Correct 6 ms 9632 KB Output is correct
72 Correct 6 ms 9452 KB Output is correct
73 Correct 6 ms 9556 KB Output is correct
74 Correct 155 ms 30552 KB Output is correct
75 Correct 215 ms 35048 KB Output is correct
76 Correct 200 ms 31452 KB Output is correct
77 Correct 158 ms 29316 KB Output is correct
78 Correct 98 ms 23648 KB Output is correct
79 Correct 85 ms 19944 KB Output is correct
80 Correct 144 ms 27564 KB Output is correct
81 Correct 248 ms 39792 KB Output is correct
82 Correct 231 ms 37024 KB Output is correct
83 Correct 292 ms 44676 KB Output is correct
84 Correct 123 ms 26440 KB Output is correct
85 Correct 200 ms 34892 KB Output is correct
86 Correct 127 ms 17816 KB Output is correct
87 Correct 396 ms 39248 KB Output is correct
88 Correct 426 ms 39468 KB Output is correct
89 Correct 403 ms 32632 KB Output is correct
90 Correct 337 ms 27560 KB Output is correct
91 Correct 364 ms 28148 KB Output is correct
92 Correct 443 ms 31388 KB Output is correct
93 Correct 479 ms 43528 KB Output is correct
94 Correct 533 ms 41264 KB Output is correct
95 Correct 470 ms 49020 KB Output is correct
96 Correct 340 ms 31596 KB Output is correct
97 Correct 455 ms 36768 KB Output is correct