oj.uz

Submission #310488

# Submission time Handle Problem Language Result Execution time Memory
310488 2020-10-07T06:05:29 Z wiwiho Swapping Cities (APIO20_swap) C++14
100 / 100
 681 ms 75928 KB 
//#define NDEBUG

#include "swap.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

vector<int> dsu, one, three;
vector<vector<int>> anc, g;
vector<int> ans, in, out;

int findDSU(int a){
    if(dsu[a] != a) dsu[a] = findDSU(dsu[a]);
    return dsu[a];
}

void unionDSU(int a, int b){
    a = findDSU(a); b = findDSU(b);
    if(a == b) return;
    dsu[b] = a;
    one[a] += one[b];
    three[a] += three[b];
}

int dfsts = 0;
void dfs(int now, int p){
    in[now] = dfsts++;
    if(ans[now] == -1) ans[now] = ans[p];
    for(int i : g[now]) dfs(i, now);
    out[now] = dfsts++;
}

bool isAnc(int a, int b){
    return in[a] <= in[b] && out[a] >= out[b];
}

int lca(int a, int b){
    if(isAnc(a, b)) return a;
    for(int i = 19; i >= 0; i--){
        if(!isAnc(anc[a][i], b)) a = anc[a][i];
    }
    return anc[a][0];
}


void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

    vector<pair<int, pii>> e(M);
    for(int i = 0; i < M; i++){
        e[i] = mp(W[i], mp(U[i], V[i]));
    }
    lsort(e);

    dsu.resize(N + M);
    for(int i = 0; i < N + M; i++) dsu[i] = i;
    one.resize(N + M); three.resize(N + M);

    int ts = N;

    anc.resize(N + M, vector<int>(20));
    for(int i = 0; i < N + M; i++) anc[i][0] = i;
    ans.resize(N + M, -1);
    g.resize(N + M);
    in.resize(N + M);
    out.resize(N + M);

    vector<int> deg(N);

    for(auto i : e){
        int w = i.F, u = i.S.F, v = i.S.S;
        if(deg[u] == 1) one[findDSU(u)]--;
        if(deg[v] == 1) one[findDSU(v)]--;
        deg[u]++; deg[v]++;
        if(deg[u] == 1) one[findDSU(u)]++;
        else if(deg[u] == 3) three[findDSU(u)]++;
        if(deg[v] == 1) one[findDSU(v)]++;
        else if(deg[v] == 3) three[findDSU(v)]++;

        u = findDSU(u);
        v = findDSU(v);
        int dv = ts++;
        if(u == v){
            unionDSU(dv, u);
            anc[u][0] = dv;
            g[dv].eb(u);
        }
        else{
            unionDSU(dv, u);
            unionDSU(dv, v);
            anc[u][0] = anc[v][0] = dv;
            g[dv].eb(u); g[dv].eb(v);
        }

        if(!one[dv] || three[dv]) ans[dv] = w;
    }

//    for(int i = 0; i < N + M; i++) cerr << anc[i][0] << " ";
//    cerr << "\n";

    for(int i = 0; i < N + M; i++){
        if(anc[i][0] == i) dfs(i, i);
    }

    for(int i = 1; i < 20; i++){
        for(int j = 0; j < N + M; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
        }
    }

}

int getMinimumFuelCapacity(int X, int Y) {
    if(findDSU(X) != findDSU(Y)) return -1;
    return ans[lca(X, Y)];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 175 ms 33400 KB Output is correct
10 Correct 223 ms 40696 KB Output is correct
11 Correct 212 ms 40056 KB Output is correct
12 Correct 225 ms 42456 KB Output is correct
13 Correct 206 ms 44788 KB Output is correct
14 Correct 192 ms 33704 KB Output is correct
15 Correct 372 ms 44792 KB Output is correct
16 Correct 381 ms 43768 KB Output is correct
17 Correct 397 ms 46200 KB Output is correct
18 Correct 491 ms 48760 KB Output is correct
19 Correct 127 ms 11968 KB Output is correct
20 Correct 368 ms 44928 KB Output is correct
21 Correct 382 ms 43524 KB Output is correct
22 Correct 375 ms 46272 KB Output is correct
23 Correct 495 ms 48708 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 485 ms 47948 KB Output is correct
4 Correct 484 ms 50168 KB Output is correct
5 Correct 499 ms 49072 KB Output is correct
6 Correct 474 ms 49912 KB Output is correct
7 Correct 485 ms 49528 KB Output is correct
8 Correct 471 ms 47848 KB Output is correct
9 Correct 482 ms 49272 KB Output is correct
10 Correct 470 ms 47244 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 2 ms 896 KB Output is correct
17 Correct 2 ms 768 KB Output is correct
18 Correct 2 ms 768 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 2 ms 768 KB Output is correct
21 Correct 2 ms 768 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 2 ms 640 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 3 ms 1024 KB Output is correct
26 Correct 3 ms 1024 KB Output is correct
27 Correct 2 ms 768 KB Output is correct
28 Correct 3 ms 1024 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 175 ms 33400 KB Output is correct
11 Correct 223 ms 40696 KB Output is correct
12 Correct 212 ms 40056 KB Output is correct
13 Correct 225 ms 42456 KB Output is correct
14 Correct 206 ms 44788 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 2 ms 768 KB Output is correct
17 Correct 2 ms 768 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Correct 1 ms 640 KB Output is correct
20 Correct 2 ms 768 KB Output is correct
21 Correct 2 ms 896 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 768 KB Output is correct
24 Correct 21 ms 6016 KB Output is correct
25 Correct 219 ms 42160 KB Output is correct
26 Correct 214 ms 42104 KB Output is correct
27 Correct 210 ms 41976 KB Output is correct
28 Correct 204 ms 41592 KB Output is correct
29 Correct 209 ms 41336 KB Output is correct
30 Correct 189 ms 37908 KB Output is correct
31 Correct 216 ms 42488 KB Output is correct
32 Correct 210 ms 42232 KB Output is correct
33 Correct 205 ms 45180 KB Output is correct
34 Correct 223 ms 42360 KB Output is correct
35 Correct 2 ms 640 KB Output is correct
36 Correct 2 ms 768 KB Output is correct
37 Correct 2 ms 768 KB Output is correct
38 Correct 3 ms 896 KB Output is correct
39 Correct 2 ms 640 KB Output is correct
40 Correct 3 ms 896 KB Output is correct
41 Correct 3 ms 1024 KB Output is correct
42 Correct 3 ms 1024 KB Output is correct
43 Correct 2 ms 768 KB Output is correct
44 Correct 3 ms 1024 KB Output is correct
45 Correct 283 ms 54904 KB Output is correct
46 Correct 199 ms 42104 KB Output is correct
47 Correct 215 ms 42104 KB Output is correct
48 Correct 239 ms 46200 KB Output is correct
49 Correct 185 ms 47096 KB Output is correct
50 Correct 153 ms 37144 KB Output is correct
51 Correct 240 ms 47480 KB Output is correct
52 Correct 312 ms 60764 KB Output is correct
53 Correct 358 ms 64892 KB Output is correct
54 Correct 352 ms 71928 KB Output is correct
55 Correct 206 ms 44920 KB Output is correct
56 Correct 360 ms 65272 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 175 ms 33400 KB Output is correct
10 Correct 223 ms 40696 KB Output is correct
11 Correct 212 ms 40056 KB Output is correct
12 Correct 225 ms 42456 KB Output is correct
13 Correct 206 ms 44788 KB Output is correct
14 Correct 192 ms 33704 KB Output is correct
15 Correct 372 ms 44792 KB Output is correct
16 Correct 381 ms 43768 KB Output is correct
17 Correct 397 ms 46200 KB Output is correct
18 Correct 491 ms 48760 KB Output is correct
19 Correct 485 ms 47948 KB Output is correct
20 Correct 484 ms 50168 KB Output is correct
21 Correct 499 ms 49072 KB Output is correct
22 Correct 474 ms 49912 KB Output is correct
23 Correct 485 ms 49528 KB Output is correct
24 Correct 471 ms 47848 KB Output is correct
25 Correct 482 ms 49272 KB Output is correct
26 Correct 470 ms 47244 KB Output is correct
27 Correct 2 ms 768 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 2 ms 768 KB Output is correct
30 Correct 1 ms 640 KB Output is correct
31 Correct 1 ms 640 KB Output is correct
32 Correct 2 ms 768 KB Output is correct
33 Correct 2 ms 896 KB Output is correct
34 Correct 2 ms 768 KB Output is correct
35 Correct 2 ms 768 KB Output is correct
36 Correct 21 ms 6016 KB Output is correct
37 Correct 219 ms 42160 KB Output is correct
38 Correct 214 ms 42104 KB Output is correct
39 Correct 210 ms 41976 KB Output is correct
40 Correct 204 ms 41592 KB Output is correct
41 Correct 209 ms 41336 KB Output is correct
42 Correct 189 ms 37908 KB Output is correct
43 Correct 216 ms 42488 KB Output is correct
44 Correct 210 ms 42232 KB Output is correct
45 Correct 205 ms 45180 KB Output is correct
46 Correct 223 ms 42360 KB Output is correct
47 Correct 32 ms 5888 KB Output is correct
48 Correct 371 ms 45944 KB Output is correct
49 Correct 383 ms 46200 KB Output is correct
50 Correct 382 ms 45816 KB Output is correct
51 Correct 380 ms 45688 KB Output is correct
52 Correct 372 ms 43256 KB Output is correct
53 Correct 296 ms 32992 KB Output is correct
54 Correct 382 ms 46532 KB Output is correct
55 Correct 370 ms 45944 KB Output is correct
56 Correct 472 ms 48416 KB Output is correct
57 Correct 398 ms 46396 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 175 ms 33400 KB Output is correct
11 Correct 223 ms 40696 KB Output is correct
12 Correct 212 ms 40056 KB Output is correct
13 Correct 225 ms 42456 KB Output is correct
14 Correct 206 ms 44788 KB Output is correct
15 Correct 192 ms 33704 KB Output is correct
16 Correct 372 ms 44792 KB Output is correct
17 Correct 381 ms 43768 KB Output is correct
18 Correct 397 ms 46200 KB Output is correct
19 Correct 491 ms 48760 KB Output is correct
20 Correct 485 ms 47948 KB Output is correct
21 Correct 484 ms 50168 KB Output is correct
22 Correct 499 ms 49072 KB Output is correct
23 Correct 474 ms 49912 KB Output is correct
24 Correct 485 ms 49528 KB Output is correct
25 Correct 471 ms 47848 KB Output is correct
26 Correct 482 ms 49272 KB Output is correct
27 Correct 470 ms 47244 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 2 ms 768 KB Output is correct
30 Correct 2 ms 768 KB Output is correct
31 Correct 1 ms 640 KB Output is correct
32 Correct 1 ms 640 KB Output is correct
33 Correct 2 ms 768 KB Output is correct
34 Correct 2 ms 896 KB Output is correct
35 Correct 2 ms 768 KB Output is correct
36 Correct 2 ms 768 KB Output is correct
37 Correct 21 ms 6016 KB Output is correct
38 Correct 219 ms 42160 KB Output is correct
39 Correct 214 ms 42104 KB Output is correct
40 Correct 210 ms 41976 KB Output is correct
41 Correct 204 ms 41592 KB Output is correct
42 Correct 209 ms 41336 KB Output is correct
43 Correct 189 ms 37908 KB Output is correct
44 Correct 216 ms 42488 KB Output is correct
45 Correct 210 ms 42232 KB Output is correct
46 Correct 205 ms 45180 KB Output is correct
47 Correct 223 ms 42360 KB Output is correct
48 Correct 32 ms 5888 KB Output is correct
49 Correct 371 ms 45944 KB Output is correct
50 Correct 383 ms 46200 KB Output is correct
51 Correct 382 ms 45816 KB Output is correct
52 Correct 380 ms 45688 KB Output is correct
53 Correct 372 ms 43256 KB Output is correct
54 Correct 296 ms 32992 KB Output is correct
55 Correct 382 ms 46532 KB Output is correct
56 Correct 370 ms 45944 KB Output is correct
57 Correct 472 ms 48416 KB Output is correct
58 Correct 398 ms 46396 KB Output is correct
59 Correct 127 ms 11968 KB Output is correct
60 Correct 368 ms 44928 KB Output is correct
61 Correct 382 ms 43524 KB Output is correct
62 Correct 375 ms 46272 KB Output is correct
63 Correct 495 ms 48708 KB Output is correct
64 Correct 2 ms 640 KB Output is correct
65 Correct 2 ms 768 KB Output is correct
66 Correct 2 ms 768 KB Output is correct
67 Correct 3 ms 896 KB Output is correct
68 Correct 2 ms 640 KB Output is correct
69 Correct 3 ms 896 KB Output is correct
70 Correct 3 ms 1024 KB Output is correct
71 Correct 3 ms 1024 KB Output is correct
72 Correct 2 ms 768 KB Output is correct
73 Correct 3 ms 1024 KB Output is correct
74 Correct 283 ms 54904 KB Output is correct
75 Correct 199 ms 42104 KB Output is correct
76 Correct 215 ms 42104 KB Output is correct
77 Correct 239 ms 46200 KB Output is correct
78 Correct 185 ms 47096 KB Output is correct
79 Correct 153 ms 37144 KB Output is correct
80 Correct 240 ms 47480 KB Output is correct
81 Correct 312 ms 60764 KB Output is correct
82 Correct 358 ms 64892 KB Output is correct
83 Correct 352 ms 71928 KB Output is correct
84 Correct 206 ms 44920 KB Output is correct
85 Correct 360 ms 65272 KB Output is correct
86 Correct 142 ms 20472 KB Output is correct
87 Correct 383 ms 46200 KB Output is correct
88 Correct 387 ms 45944 KB Output is correct
89 Correct 509 ms 47864 KB Output is correct
90 Correct 314 ms 53240 KB Output is correct
91 Correct 346 ms 49656 KB Output is correct
92 Correct 528 ms 49400 KB Output is correct
93 Correct 509 ms 63736 KB Output is correct
94 Correct 681 ms 68728 KB Output is correct
95 Correct 565 ms 75928 KB Output is correct
96 Correct 526 ms 48504 KB Output is correct
97 Correct 629 ms 58104 KB Output is correct