oj.uz

Submission #429651

# Submission time Handle Problem Language Result Execution time Memory
429651 2021-06-16T08:24:25 Z snasibov05 Swapping Cities (APIO20_swap) C++14
100 / 100
 409 ms 32056 KB 
#include "swap.h"
#include <vector>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define oo 1000000001

struct edge{
    int u, v;
    int w;

    bool operator< (edge e) const{
        return w < e.w;
    }
};


vector<int> pr;
vector<edge> ed;
vector<int> deg;
vector<vector<int>> cmp;
vector<vector<pii>> arr;
vector<int> when;

void Union(edge e){
    deg[e.u]++; deg[e.v]++;

    int x = pr[e.u]; int y = pr[e.v];

    if (x == y){
        when[x] = min(when[x], e.w);
        return;
    }

    if (cmp[x].size() < cmp[y].size()) swap(x, y);

    for (auto node : cmp[y]){
        cmp[x].pb(node);
        pr[node] = x;
        arr[node].pb({x, e.w});
    }

    cmp[y].clear();
    if (when[y] != oo) when[x] = min(when[x], e.w);
    if (deg[e.u] >= 3 || deg[e.v] >= 3) when[x] = min(when[x], e.w);
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    pr.resize(n);
    ed.resize(m);
    deg.resize(n);
    cmp.resize(n);
    arr.resize(n);
    when.resize(n);

    for (int i = 0; i < m; ++i) {
        ed[i].u = u[i];
        ed[i].v = v[i];
        ed[i].w = w[i];
    }

    for (int i = 0; i < n; ++i) {
        pr[i] = i;
        cmp[i].pb(i);
        deg[i] = 0;
        arr[i].pb({i, 0});
        when[i] = oo;
    }


    sort(ed.begin(), ed.end());

    for (int i = 0; i < m; ++i) {
        Union(ed[i]);
    }

}

int getMinimumFuelCapacity(int x, int y) {

    int ans = 0;
    if (when[pr[x]] == oo) return -1;
    int cmpx = x, cmpy = y;
    int a = 0, b = 0;

    while (cmpx != cmpy || when[cmpx] == oo){
        if (a == arr[x].size() || (b != arr[y].size() && arr[y][b].s < arr[x][a].s)){
            cmpy = arr[y][b].f;
            ans = max(ans, arr[y][b++].s);
        } else {
            cmpx = arr[x][a].f;
            ans = max(ans, arr[x][a++].s);
        }
    }

    ans = max(ans, when[cmpx]);

    return ans;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if (a == arr[x].size() || (b != arr[y].size() && arr[y][b].s < arr[x][a].s)){
      |             ~~^~~~~~~~~~~~~~~~
swap.cpp:92:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if (a == arr[x].size() || (b != arr[y].size() && arr[y][b].s < arr[x][a].s)){
      |                                    ~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 157 ms 20928 KB Output is correct
10 Correct 207 ms 25224 KB Output is correct
11 Correct 212 ms 24788 KB Output is correct
12 Correct 226 ms 26284 KB Output is correct
13 Correct 127 ms 18928 KB Output is correct
14 Correct 162 ms 20920 KB Output is correct
15 Correct 287 ms 27552 KB Output is correct
16 Correct 267 ms 26604 KB Output is correct
17 Correct 288 ms 28496 KB Output is correct
18 Correct 172 ms 20580 KB Output is correct
19 Correct 89 ms 7608 KB Output is correct
20 Correct 323 ms 28704 KB Output is correct
21 Correct 335 ms 28068 KB Output is correct
22 Correct 337 ms 29584 KB Output is correct
23 Correct 255 ms 22300 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 178 ms 18524 KB Output is correct
4 Correct 227 ms 19224 KB Output is correct
5 Correct 219 ms 18984 KB Output is correct
6 Correct 191 ms 19144 KB Output is correct
7 Correct 211 ms 19104 KB Output is correct
8 Correct 192 ms 18544 KB Output is correct
9 Correct 194 ms 19004 KB Output is correct
10 Correct 183 ms 18328 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 157 ms 20928 KB Output is correct
11 Correct 207 ms 25224 KB Output is correct
12 Correct 212 ms 24788 KB Output is correct
13 Correct 226 ms 26284 KB Output is correct
14 Correct 127 ms 18928 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 15 ms 3404 KB Output is correct
35 Correct 256 ms 26148 KB Output is correct
36 Correct 219 ms 25884 KB Output is correct
37 Correct 271 ms 25420 KB Output is correct
38 Correct 294 ms 24592 KB Output is correct
39 Correct 220 ms 24232 KB Output is correct
40 Correct 173 ms 21668 KB Output is correct
41 Correct 266 ms 26664 KB Output is correct
42 Correct 227 ms 26688 KB Output is correct
43 Correct 124 ms 18008 KB Output is correct
44 Correct 211 ms 23996 KB Output is correct
45 Correct 132 ms 18008 KB Output is correct
46 Correct 214 ms 25824 KB Output is correct
47 Correct 169 ms 22440 KB Output is correct
48 Correct 137 ms 19644 KB Output is correct
49 Correct 64 ms 5984 KB Output is correct
50 Correct 51 ms 5660 KB Output is correct
51 Correct 103 ms 14784 KB Output is correct
52 Correct 244 ms 27296 KB Output is correct
53 Correct 195 ms 23384 KB Output is correct
54 Correct 281 ms 30188 KB Output is correct
55 Correct 115 ms 18324 KB Output is correct
56 Correct 176 ms 22260 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 157 ms 20928 KB Output is correct
10 Correct 207 ms 25224 KB Output is correct
11 Correct 212 ms 24788 KB Output is correct
12 Correct 226 ms 26284 KB Output is correct
13 Correct 127 ms 18928 KB Output is correct
14 Correct 162 ms 20920 KB Output is correct
15 Correct 287 ms 27552 KB Output is correct
16 Correct 267 ms 26604 KB Output is correct
17 Correct 288 ms 28496 KB Output is correct
18 Correct 172 ms 20580 KB Output is correct
19 Correct 178 ms 18524 KB Output is correct
20 Correct 227 ms 19224 KB Output is correct
21 Correct 219 ms 18984 KB Output is correct
22 Correct 191 ms 19144 KB Output is correct
23 Correct 211 ms 19104 KB Output is correct
24 Correct 192 ms 18544 KB Output is correct
25 Correct 194 ms 19004 KB Output is correct
26 Correct 183 ms 18328 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 1 ms 460 KB Output is correct
36 Correct 15 ms 3404 KB Output is correct
37 Correct 256 ms 26148 KB Output is correct
38 Correct 219 ms 25884 KB Output is correct
39 Correct 271 ms 25420 KB Output is correct
40 Correct 294 ms 24592 KB Output is correct
41 Correct 220 ms 24232 KB Output is correct
42 Correct 173 ms 21668 KB Output is correct
43 Correct 266 ms 26664 KB Output is correct
44 Correct 227 ms 26688 KB Output is correct
45 Correct 124 ms 18008 KB Output is correct
46 Correct 211 ms 23996 KB Output is correct
47 Correct 22 ms 3532 KB Output is correct
48 Correct 362 ms 28844 KB Output is correct
49 Correct 333 ms 28200 KB Output is correct
50 Correct 346 ms 28216 KB Output is correct
51 Correct 364 ms 27680 KB Output is correct
52 Correct 300 ms 25776 KB Output is correct
53 Correct 230 ms 19220 KB Output is correct
54 Correct 340 ms 29192 KB Output is correct
55 Correct 361 ms 29488 KB Output is correct
56 Correct 210 ms 21300 KB Output is correct
57 Correct 328 ms 26900 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 157 ms 20928 KB Output is correct
11 Correct 207 ms 25224 KB Output is correct
12 Correct 212 ms 24788 KB Output is correct
13 Correct 226 ms 26284 KB Output is correct
14 Correct 127 ms 18928 KB Output is correct
15 Correct 162 ms 20920 KB Output is correct
16 Correct 287 ms 27552 KB Output is correct
17 Correct 267 ms 26604 KB Output is correct
18 Correct 288 ms 28496 KB Output is correct
19 Correct 172 ms 20580 KB Output is correct
20 Correct 178 ms 18524 KB Output is correct
21 Correct 227 ms 19224 KB Output is correct
22 Correct 219 ms 18984 KB Output is correct
23 Correct 191 ms 19144 KB Output is correct
24 Correct 211 ms 19104 KB Output is correct
25 Correct 192 ms 18544 KB Output is correct
26 Correct 194 ms 19004 KB Output is correct
27 Correct 183 ms 18328 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 2 ms 460 KB Output is correct
35 Correct 1 ms 460 KB Output is correct
36 Correct 1 ms 460 KB Output is correct
37 Correct 15 ms 3404 KB Output is correct
38 Correct 256 ms 26148 KB Output is correct
39 Correct 219 ms 25884 KB Output is correct
40 Correct 271 ms 25420 KB Output is correct
41 Correct 294 ms 24592 KB Output is correct
42 Correct 220 ms 24232 KB Output is correct
43 Correct 173 ms 21668 KB Output is correct
44 Correct 266 ms 26664 KB Output is correct
45 Correct 227 ms 26688 KB Output is correct
46 Correct 124 ms 18008 KB Output is correct
47 Correct 211 ms 23996 KB Output is correct
48 Correct 22 ms 3532 KB Output is correct
49 Correct 362 ms 28844 KB Output is correct
50 Correct 333 ms 28200 KB Output is correct
51 Correct 346 ms 28216 KB Output is correct
52 Correct 364 ms 27680 KB Output is correct
53 Correct 300 ms 25776 KB Output is correct
54 Correct 230 ms 19220 KB Output is correct
55 Correct 340 ms 29192 KB Output is correct
56 Correct 361 ms 29488 KB Output is correct
57 Correct 210 ms 21300 KB Output is correct
58 Correct 328 ms 26900 KB Output is correct
59 Correct 89 ms 7608 KB Output is correct
60 Correct 323 ms 28704 KB Output is correct
61 Correct 335 ms 28068 KB Output is correct
62 Correct 337 ms 29584 KB Output is correct
63 Correct 255 ms 22300 KB Output is correct
64 Correct 2 ms 332 KB Output is correct
65 Correct 1 ms 460 KB Output is correct
66 Correct 1 ms 460 KB Output is correct
67 Correct 2 ms 332 KB Output is correct
68 Correct 1 ms 332 KB Output is correct
69 Correct 2 ms 460 KB Output is correct
70 Correct 2 ms 460 KB Output is correct
71 Correct 2 ms 460 KB Output is correct
72 Correct 1 ms 332 KB Output is correct
73 Correct 2 ms 460 KB Output is correct
74 Correct 132 ms 18008 KB Output is correct
75 Correct 214 ms 25824 KB Output is correct
76 Correct 169 ms 22440 KB Output is correct
77 Correct 137 ms 19644 KB Output is correct
78 Correct 64 ms 5984 KB Output is correct
79 Correct 51 ms 5660 KB Output is correct
80 Correct 103 ms 14784 KB Output is correct
81 Correct 244 ms 27296 KB Output is correct
82 Correct 195 ms 23384 KB Output is correct
83 Correct 281 ms 30188 KB Output is correct
84 Correct 115 ms 18324 KB Output is correct
85 Correct 176 ms 22260 KB Output is correct
86 Correct 60 ms 7404 KB Output is correct
87 Correct 356 ms 27892 KB Output is correct
88 Correct 325 ms 27980 KB Output is correct
89 Correct 229 ms 21036 KB Output is correct
90 Correct 135 ms 8500 KB Output is correct
91 Correct 140 ms 9652 KB Output is correct
92 Correct 208 ms 17688 KB Output is correct
93 Correct 357 ms 29008 KB Output is correct
94 Correct 302 ms 26016 KB Output is correct
95 Correct 409 ms 32056 KB Output is correct
96 Correct 209 ms 21156 KB Output is correct
97 Correct 263 ms 23976 KB Output is correct