oj.uz

Submission #673955

# Submission time Handle Problem Language Result Execution time Memory
673955 2022-12-22T13:02:52 Z c2zi6 Swapping Cities (APIO20_swap) C++14
100 / 100
 417 ms 17876 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

struct EDGE {
    int u, v, w;
};

struct DSUNODE;
vector<DSUNODE> nodes;
struct DSUNODE {
    int vert;
    int parent;
    int distToParent;
    int size;
    int left;
    int right;
    int when;
    int leader(int mxpath = 2e9) {
        if (parent == -1 || distToParent > mxpath) return vert;
        return nodes[nodes[parent].leader(mxpath)].vert;
    }
};

vector<EDGE> edges;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    edges = vector<EDGE>(M);
    nodes = vector<DSUNODE>(N);
    for (int i = 0; i < N; i++) {
        DSUNODE& a = nodes[i];
        a.parent = -1;
        a.distToParent = 0;
        a.size = 1;
        a.vert = a.left = a.right = i;
        a.when = 2e9;
    }
    for (int i = 0; i < M; i++) {
        edges[i] = {U[i], V[i], W[i]};
    }
    sort(edges.begin(), edges.end(), [](const EDGE& a, const EDGE& b){return a.w < b.w;});
    //cout << "WORKS" << endl;
    for (int i = 0; i < M; i++) {
        //cout << nodes[edges[i].u].leader() << " " << nodes[edges[i].v].leader() << endl;
        DSUNODE& u = nodes[nodes[edges[i].u].leader()];
        DSUNODE& v = nodes[nodes[edges[i].v].leader()];
        if (u.vert == v.vert) {
            u.left = -1;
            u.right = -1;
            u.when = min(u.when, edges[i].w);
            continue;
        }

        int newleft = -1, newright = -1;
        if (edges[i].u == u.left && edges[i].v == v.left) {
            newleft = u.right;
            newright = v.right;
        } else if (edges[i].u == u.left && edges[i].v == v.right) {
            newleft = u.right;
            newright = v.left;
        } else if (edges[i].u == u.right && edges[i].v == v.left) {
            newleft = u.left;
            newright = v.right;
        } else if (edges[i].u == u.right && edges[i].v == v.right) {
            newleft = u.left;
            newright = v.left;
        }

        if (u.size > v.size) {
            v.parent = u.vert;
            v.distToParent = edges[i].w;
            u.size += v.size;
            u.left = newleft;
            u.right = newright;
            if (newleft == -1) {
                u.when = min(u.when, edges[i].w);
            }
        } else {
            u.parent = v.vert;
            u.distToParent = edges[i].w;
            v.size += u.size;
            v.left = newleft;
            v.right = newright;
            if (newleft == -1) {
                v.when = min(v.when, edges[i].w);
            }
        }
    }
}

bool can(int X, int Y, int M) {
    int u = nodes[X].leader(M), v = nodes[Y].leader(M);
    return u == v && M >= nodes[u].when;
}

int getMinimumFuelCapacity(int X, int Y) {
    if (!can(X, Y, 1e9)) return -1;
    int l = 0, r = 1e9;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (can(X, Y, m)) r = m;
        else l = m;
    }
    return r;
}

int mai2n() {
  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;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 35 ms 5196 KB Output is correct
10 Correct 43 ms 6220 KB Output is correct
11 Correct 39 ms 6156 KB Output is correct
12 Correct 42 ms 6596 KB Output is correct
13 Correct 39 ms 6476 KB Output is correct
14 Correct 39 ms 5320 KB Output is correct
15 Correct 116 ms 8120 KB Output is correct
16 Correct 115 ms 7996 KB Output is correct
17 Correct 122 ms 8264 KB Output is correct
18 Correct 99 ms 8244 KB Output is correct
19 Correct 202 ms 4672 KB Output is correct
20 Correct 310 ms 9264 KB Output is correct
21 Correct 330 ms 9352 KB Output is correct
22 Correct 342 ms 9664 KB Output is correct
23 Correct 132 ms 9652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 136 ms 9136 KB Output is correct
4 Correct 139 ms 9384 KB Output is correct
5 Correct 146 ms 9540 KB Output is correct
6 Correct 137 ms 9216 KB Output is correct
7 Correct 138 ms 9512 KB Output is correct
8 Correct 137 ms 9244 KB Output is correct
9 Correct 152 ms 9304 KB Output is correct
10 Correct 132 ms 9220 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 35 ms 5196 KB Output is correct
11 Correct 43 ms 6220 KB Output is correct
12 Correct 39 ms 6156 KB Output is correct
13 Correct 42 ms 6596 KB Output is correct
14 Correct 39 ms 6476 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 6 ms 1108 KB Output is correct
35 Correct 39 ms 6468 KB Output is correct
36 Correct 38 ms 6476 KB Output is correct
37 Correct 38 ms 6476 KB Output is correct
38 Correct 38 ms 6452 KB Output is correct
39 Correct 38 ms 6324 KB Output is correct
40 Correct 35 ms 5844 KB Output is correct
41 Correct 41 ms 6468 KB Output is correct
42 Correct 38 ms 6476 KB Output is correct
43 Correct 38 ms 6484 KB Output is correct
44 Correct 44 ms 6472 KB Output is correct
45 Correct 63 ms 10728 KB Output is correct
46 Correct 43 ms 8368 KB Output is correct
47 Correct 40 ms 8248 KB Output is correct
48 Correct 44 ms 8780 KB Output is correct
49 Correct 59 ms 8548 KB Output is correct
50 Correct 50 ms 6940 KB Output is correct
51 Correct 57 ms 9212 KB Output is correct
52 Correct 75 ms 12036 KB Output is correct
53 Correct 80 ms 13124 KB Output is correct
54 Correct 95 ms 14116 KB Output is correct
55 Correct 41 ms 8368 KB Output is correct
56 Correct 77 ms 12668 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 35 ms 5196 KB Output is correct
10 Correct 43 ms 6220 KB Output is correct
11 Correct 39 ms 6156 KB Output is correct
12 Correct 42 ms 6596 KB Output is correct
13 Correct 39 ms 6476 KB Output is correct
14 Correct 39 ms 5320 KB Output is correct
15 Correct 116 ms 8120 KB Output is correct
16 Correct 115 ms 7996 KB Output is correct
17 Correct 122 ms 8264 KB Output is correct
18 Correct 99 ms 8244 KB Output is correct
19 Correct 136 ms 9136 KB Output is correct
20 Correct 139 ms 9384 KB Output is correct
21 Correct 146 ms 9540 KB Output is correct
22 Correct 137 ms 9216 KB Output is correct
23 Correct 138 ms 9512 KB Output is correct
24 Correct 137 ms 9244 KB Output is correct
25 Correct 152 ms 9304 KB Output is correct
26 Correct 132 ms 9220 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 6 ms 1108 KB Output is correct
37 Correct 39 ms 6468 KB Output is correct
38 Correct 38 ms 6476 KB Output is correct
39 Correct 38 ms 6476 KB Output is correct
40 Correct 38 ms 6452 KB Output is correct
41 Correct 38 ms 6324 KB Output is correct
42 Correct 35 ms 5844 KB Output is correct
43 Correct 41 ms 6468 KB Output is correct
44 Correct 38 ms 6476 KB Output is correct
45 Correct 38 ms 6484 KB Output is correct
46 Correct 44 ms 6472 KB Output is correct
47 Correct 27 ms 1364 KB Output is correct
48 Correct 366 ms 9072 KB Output is correct
49 Correct 332 ms 9144 KB Output is correct
50 Correct 327 ms 9136 KB Output is correct
51 Correct 300 ms 9040 KB Output is correct
52 Correct 280 ms 8688 KB Output is correct
53 Correct 241 ms 7924 KB Output is correct
54 Correct 355 ms 9748 KB Output is correct
55 Correct 363 ms 9140 KB Output is correct
56 Correct 138 ms 9024 KB Output is correct
57 Correct 265 ms 9676 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 35 ms 5196 KB Output is correct
11 Correct 43 ms 6220 KB Output is correct
12 Correct 39 ms 6156 KB Output is correct
13 Correct 42 ms 6596 KB Output is correct
14 Correct 39 ms 6476 KB Output is correct
15 Correct 39 ms 5320 KB Output is correct
16 Correct 116 ms 8120 KB Output is correct
17 Correct 115 ms 7996 KB Output is correct
18 Correct 122 ms 8264 KB Output is correct
19 Correct 99 ms 8244 KB Output is correct
20 Correct 136 ms 9136 KB Output is correct
21 Correct 139 ms 9384 KB Output is correct
22 Correct 146 ms 9540 KB Output is correct
23 Correct 137 ms 9216 KB Output is correct
24 Correct 138 ms 9512 KB Output is correct
25 Correct 137 ms 9244 KB Output is correct
26 Correct 152 ms 9304 KB Output is correct
27 Correct 132 ms 9220 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 6 ms 1108 KB Output is correct
38 Correct 39 ms 6468 KB Output is correct
39 Correct 38 ms 6476 KB Output is correct
40 Correct 38 ms 6476 KB Output is correct
41 Correct 38 ms 6452 KB Output is correct
42 Correct 38 ms 6324 KB Output is correct
43 Correct 35 ms 5844 KB Output is correct
44 Correct 41 ms 6468 KB Output is correct
45 Correct 38 ms 6476 KB Output is correct
46 Correct 38 ms 6484 KB Output is correct
47 Correct 44 ms 6472 KB Output is correct
48 Correct 27 ms 1364 KB Output is correct
49 Correct 366 ms 9072 KB Output is correct
50 Correct 332 ms 9144 KB Output is correct
51 Correct 327 ms 9136 KB Output is correct
52 Correct 300 ms 9040 KB Output is correct
53 Correct 280 ms 8688 KB Output is correct
54 Correct 241 ms 7924 KB Output is correct
55 Correct 355 ms 9748 KB Output is correct
56 Correct 363 ms 9140 KB Output is correct
57 Correct 138 ms 9024 KB Output is correct
58 Correct 265 ms 9676 KB Output is correct
59 Correct 202 ms 4672 KB Output is correct
60 Correct 310 ms 9264 KB Output is correct
61 Correct 330 ms 9352 KB Output is correct
62 Correct 342 ms 9664 KB Output is correct
63 Correct 132 ms 9652 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 340 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 1 ms 340 KB Output is correct
68 Correct 1 ms 340 KB Output is correct
69 Correct 1 ms 340 KB Output is correct
70 Correct 1 ms 340 KB Output is correct
71 Correct 1 ms 340 KB Output is correct
72 Correct 1 ms 340 KB Output is correct
73 Correct 1 ms 340 KB Output is correct
74 Correct 63 ms 10728 KB Output is correct
75 Correct 43 ms 8368 KB Output is correct
76 Correct 40 ms 8248 KB Output is correct
77 Correct 44 ms 8780 KB Output is correct
78 Correct 59 ms 8548 KB Output is correct
79 Correct 50 ms 6940 KB Output is correct
80 Correct 57 ms 9212 KB Output is correct
81 Correct 75 ms 12036 KB Output is correct
82 Correct 80 ms 13124 KB Output is correct
83 Correct 95 ms 14116 KB Output is correct
84 Correct 41 ms 8368 KB Output is correct
85 Correct 77 ms 12668 KB Output is correct
86 Correct 58 ms 4896 KB Output is correct
87 Correct 308 ms 13252 KB Output is correct
88 Correct 315 ms 13216 KB Output is correct
89 Correct 193 ms 13152 KB Output is correct
90 Correct 190 ms 13056 KB Output is correct
91 Correct 193 ms 13216 KB Output is correct
92 Correct 202 ms 14112 KB Output is correct
93 Correct 322 ms 16672 KB Output is correct
94 Correct 253 ms 17556 KB Output is correct
95 Correct 417 ms 17876 KB Output is correct
96 Correct 153 ms 13392 KB Output is correct
97 Correct 215 ms 15648 KB Output is correct