oj.uz

Submission #736580

# Submission time Handle Problem Language Result Execution time Memory
736580 2023-05-06T01:29:47 Z GusterGoose27 Swapping Cities (APIO20_swap) C++17
100 / 100
 520 ms 48296 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MAXM = 2e5;
const int inf = 1e9;

class edge {
public:
    int u, v, w;
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    edge() {}
};

bool operator<(edge &a, edge &b) {
    return (a.w == b.w) ? (a.u == b.u) ? (a.v < b.v) : (a.u < b.u) : (a.w < b.w);
}

edge edges[MAXM];
vector<pii> par[MAXN]; // time, val
vector<int> in_set[MAXN];
map<int, int> compress;
int comp_inv[MAXM];
int nice_pos[MAXN];
pii epoints[MAXN];
int t;

void merge(int a, int b) {
    int an = par[a].back().second;
    int bn = par[b].back().second;
    if (an == bn) {
        nice_pos[an] = min(nice_pos[an], t);
        return;
    }
    if (in_set[an].size() < in_set[bn].size()) {
        swap(a, b);
        swap(an, bn);
    }
    for (int v: in_set[bn]) {
        in_set[an].push_back(v);
        par[v].push_back(pii(t, an));
    }
    if ((a == epoints[an].first || a == epoints[an].second) && 
        (b == epoints[bn].first || b == epoints[bn].second)) {
        epoints[an] = pii(epoints[an].first+epoints[an].second-a, epoints[bn].first+epoints[bn].second-b);
    }
    else {
        nice_pos[an] = min(nice_pos[an], t);
    }
    nice_pos[an] = min(nice_pos[an], max(t, nice_pos[bn]));
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < m; i++) edges[i] = edge(U[i], V[i], W[i]);
    sort(W.begin(), W.end());
    for (int w: W) {
        if (compress.find(w) == compress.end()) {
            compress[w] = compress.size();
            comp_inv[compress.size()-1] = w;
        }
    }
    for (int i = 0; i < m; i++) edges[i].w = compress[edges[i].w];
    sort(edges, edges+m);
    for (int i = 0; i < n; i++) {
        par[i].push_back(pii(-1, i));
        in_set[i].push_back(i);
        nice_pos[i] = inf;
        epoints[i] = pii(i, i);
    }
    int j = 0;
    for (int i = 0; i < compress.size(); i++) {
        t = i;
        while (j < m && edges[j].w == i) {
            merge(edges[j].u, edges[j].v);
            j++;
        }
    }
}

int get_par(int x, int cur) {
    int mn = 0;
    int mx = par[x].size();
    while (mx > mn+1) {
        int cval = (mn+mx)/2;
        if (par[x][cval].first <= cur) mn = cval;
        else mx = cval;
    }
    return par[x][mn].second;
}

int getMinimumFuelCapacity(int x, int y) {
    int mn = -1;
    int mx = compress.size();
    while (mx > mn+1) {
        int cur = (mn+mx)/2;
        int p1 = get_par(x, cur);
        int p2 = get_par(y, cur);
        if (p1 == p2 && nice_pos[p1] <= cur) mx = cur;
        else mn = cur;
    }
    if (mx == compress.size()) {
        return -1;
    }
    return comp_inv[mx];
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < compress.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:106:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     if (mx == compress.size()) {
      |         ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5016 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 4 ms 5152 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 151 ms 25940 KB Output is correct
10 Correct 221 ms 30440 KB Output is correct
11 Correct 199 ms 29844 KB Output is correct
12 Correct 226 ms 31412 KB Output is correct
13 Correct 142 ms 24044 KB Output is correct
14 Correct 162 ms 26004 KB Output is correct
15 Correct 384 ms 32708 KB Output is correct
16 Correct 351 ms 31732 KB Output is correct
17 Correct 358 ms 33668 KB Output is correct
18 Correct 267 ms 25796 KB Output is correct
19 Correct 135 ms 12480 KB Output is correct
20 Correct 368 ms 33752 KB Output is correct
21 Correct 336 ms 33072 KB Output is correct
22 Correct 386 ms 34832 KB Output is correct
23 Correct 269 ms 27160 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 230 ms 23688 KB Output is correct
4 Correct 229 ms 24364 KB Output is correct
5 Correct 243 ms 24236 KB Output is correct
6 Correct 233 ms 24208 KB Output is correct
7 Correct 232 ms 24276 KB Output is correct
8 Correct 255 ms 23756 KB Output is correct
9 Correct 278 ms 24100 KB Output is correct
10 Correct 243 ms 23496 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 4 ms 5152 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 151 ms 25940 KB Output is correct
11 Correct 221 ms 30440 KB Output is correct
12 Correct 199 ms 29844 KB Output is correct
13 Correct 226 ms 31412 KB Output is correct
14 Correct 142 ms 24044 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 3 ms 5204 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 3 ms 5204 KB Output is correct
23 Correct 4 ms 5204 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct
25 Correct 3 ms 5204 KB Output is correct
26 Correct 4 ms 5204 KB Output is correct
27 Correct 3 ms 5076 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct
29 Correct 5 ms 5296 KB Output is correct
30 Correct 4 ms 5204 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 4 ms 5204 KB Output is correct
33 Correct 4 ms 5204 KB Output is correct
34 Correct 18 ms 8096 KB Output is correct
35 Correct 222 ms 31044 KB Output is correct
36 Correct 220 ms 30756 KB Output is correct
37 Correct 215 ms 30404 KB Output is correct
38 Correct 196 ms 29328 KB Output is correct
39 Correct 186 ms 28996 KB Output is correct
40 Correct 167 ms 26552 KB Output is correct
41 Correct 229 ms 31784 KB Output is correct
42 Correct 225 ms 31516 KB Output is correct
43 Correct 140 ms 22780 KB Output is correct
44 Correct 190 ms 29084 KB Output is correct
45 Correct 195 ms 26440 KB Output is correct
46 Correct 206 ms 30748 KB Output is correct
47 Correct 174 ms 27292 KB Output is correct
48 Correct 175 ms 25128 KB Output is correct
49 Correct 191 ms 18640 KB Output is correct
50 Correct 121 ms 16156 KB Output is correct
51 Correct 164 ms 23024 KB Output is correct
52 Correct 287 ms 35508 KB Output is correct
53 Correct 291 ms 32544 KB Output is correct
54 Correct 360 ms 40156 KB Output is correct
55 Correct 132 ms 23164 KB Output is correct
56 Correct 254 ms 31012 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5016 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 4 ms 5152 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 151 ms 25940 KB Output is correct
10 Correct 221 ms 30440 KB Output is correct
11 Correct 199 ms 29844 KB Output is correct
12 Correct 226 ms 31412 KB Output is correct
13 Correct 142 ms 24044 KB Output is correct
14 Correct 162 ms 26004 KB Output is correct
15 Correct 384 ms 32708 KB Output is correct
16 Correct 351 ms 31732 KB Output is correct
17 Correct 358 ms 33668 KB Output is correct
18 Correct 267 ms 25796 KB Output is correct
19 Correct 230 ms 23688 KB Output is correct
20 Correct 229 ms 24364 KB Output is correct
21 Correct 243 ms 24236 KB Output is correct
22 Correct 233 ms 24208 KB Output is correct
23 Correct 232 ms 24276 KB Output is correct
24 Correct 255 ms 23756 KB Output is correct
25 Correct 278 ms 24100 KB Output is correct
26 Correct 243 ms 23496 KB Output is correct
27 Correct 4 ms 5204 KB Output is correct
28 Correct 4 ms 5204 KB Output is correct
29 Correct 4 ms 5204 KB Output is correct
30 Correct 3 ms 5076 KB Output is correct
31 Correct 3 ms 5204 KB Output is correct
32 Correct 3 ms 5204 KB Output is correct
33 Correct 3 ms 5204 KB Output is correct
34 Correct 3 ms 5204 KB Output is correct
35 Correct 4 ms 5204 KB Output is correct
36 Correct 18 ms 8096 KB Output is correct
37 Correct 222 ms 31044 KB Output is correct
38 Correct 220 ms 30756 KB Output is correct
39 Correct 215 ms 30404 KB Output is correct
40 Correct 196 ms 29328 KB Output is correct
41 Correct 186 ms 28996 KB Output is correct
42 Correct 167 ms 26552 KB Output is correct
43 Correct 229 ms 31784 KB Output is correct
44 Correct 225 ms 31516 KB Output is correct
45 Correct 140 ms 22780 KB Output is correct
46 Correct 190 ms 29084 KB Output is correct
47 Correct 27 ms 8276 KB Output is correct
48 Correct 365 ms 33776 KB Output is correct
49 Correct 365 ms 33016 KB Output is correct
50 Correct 366 ms 37032 KB Output is correct
51 Correct 358 ms 36464 KB Output is correct
52 Correct 321 ms 34500 KB Output is correct
53 Correct 250 ms 27932 KB Output is correct
54 Correct 387 ms 38736 KB Output is correct
55 Correct 375 ms 38564 KB Output is correct
56 Correct 260 ms 30184 KB Output is correct
57 Correct 330 ms 36484 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 4 ms 5152 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 151 ms 25940 KB Output is correct
11 Correct 221 ms 30440 KB Output is correct
12 Correct 199 ms 29844 KB Output is correct
13 Correct 226 ms 31412 KB Output is correct
14 Correct 142 ms 24044 KB Output is correct
15 Correct 162 ms 26004 KB Output is correct
16 Correct 384 ms 32708 KB Output is correct
17 Correct 351 ms 31732 KB Output is correct
18 Correct 358 ms 33668 KB Output is correct
19 Correct 267 ms 25796 KB Output is correct
20 Correct 230 ms 23688 KB Output is correct
21 Correct 229 ms 24364 KB Output is correct
22 Correct 243 ms 24236 KB Output is correct
23 Correct 233 ms 24208 KB Output is correct
24 Correct 232 ms 24276 KB Output is correct
25 Correct 255 ms 23756 KB Output is correct
26 Correct 278 ms 24100 KB Output is correct
27 Correct 243 ms 23496 KB Output is correct
28 Correct 4 ms 5204 KB Output is correct
29 Correct 4 ms 5204 KB Output is correct
30 Correct 4 ms 5204 KB Output is correct
31 Correct 3 ms 5076 KB Output is correct
32 Correct 3 ms 5204 KB Output is correct
33 Correct 3 ms 5204 KB Output is correct
34 Correct 3 ms 5204 KB Output is correct
35 Correct 3 ms 5204 KB Output is correct
36 Correct 4 ms 5204 KB Output is correct
37 Correct 18 ms 8096 KB Output is correct
38 Correct 222 ms 31044 KB Output is correct
39 Correct 220 ms 30756 KB Output is correct
40 Correct 215 ms 30404 KB Output is correct
41 Correct 196 ms 29328 KB Output is correct
42 Correct 186 ms 28996 KB Output is correct
43 Correct 167 ms 26552 KB Output is correct
44 Correct 229 ms 31784 KB Output is correct
45 Correct 225 ms 31516 KB Output is correct
46 Correct 140 ms 22780 KB Output is correct
47 Correct 190 ms 29084 KB Output is correct
48 Correct 27 ms 8276 KB Output is correct
49 Correct 365 ms 33776 KB Output is correct
50 Correct 365 ms 33016 KB Output is correct
51 Correct 366 ms 37032 KB Output is correct
52 Correct 358 ms 36464 KB Output is correct
53 Correct 321 ms 34500 KB Output is correct
54 Correct 250 ms 27932 KB Output is correct
55 Correct 387 ms 38736 KB Output is correct
56 Correct 375 ms 38564 KB Output is correct
57 Correct 260 ms 30184 KB Output is correct
58 Correct 330 ms 36484 KB Output is correct
59 Correct 135 ms 12480 KB Output is correct
60 Correct 368 ms 33752 KB Output is correct
61 Correct 336 ms 33072 KB Output is correct
62 Correct 386 ms 34832 KB Output is correct
63 Correct 269 ms 27160 KB Output is correct
64 Correct 3 ms 5076 KB Output is correct
65 Correct 3 ms 5204 KB Output is correct
66 Correct 4 ms 5204 KB Output is correct
67 Correct 3 ms 5076 KB Output is correct
68 Correct 3 ms 5076 KB Output is correct
69 Correct 5 ms 5296 KB Output is correct
70 Correct 4 ms 5204 KB Output is correct
71 Correct 4 ms 5332 KB Output is correct
72 Correct 4 ms 5204 KB Output is correct
73 Correct 4 ms 5204 KB Output is correct
74 Correct 195 ms 26440 KB Output is correct
75 Correct 206 ms 30748 KB Output is correct
76 Correct 174 ms 27292 KB Output is correct
77 Correct 175 ms 25128 KB Output is correct
78 Correct 191 ms 18640 KB Output is correct
79 Correct 121 ms 16156 KB Output is correct
80 Correct 164 ms 23024 KB Output is correct
81 Correct 287 ms 35508 KB Output is correct
82 Correct 291 ms 32544 KB Output is correct
83 Correct 360 ms 40156 KB Output is correct
84 Correct 132 ms 23164 KB Output is correct
85 Correct 254 ms 31012 KB Output is correct
86 Correct 88 ms 14856 KB Output is correct
87 Correct 379 ms 36860 KB Output is correct
88 Correct 368 ms 37200 KB Output is correct
89 Correct 277 ms 30820 KB Output is correct
90 Correct 292 ms 26532 KB Output is correct
91 Correct 275 ms 26328 KB Output is correct
92 Correct 276 ms 30416 KB Output is correct
93 Correct 422 ms 42748 KB Output is correct
94 Correct 408 ms 41244 KB Output is correct
95 Correct 520 ms 48296 KB Output is correct
96 Correct 253 ms 30160 KB Output is correct
97 Correct 342 ms 36088 KB Output is correct