oj.uz

Submission #1059990

# Submission time Handle Problem Language Result Execution time Memory
1059990 2024-08-15T09:54:43 Z mispertion Swapping Cities (APIO20_swap) C++17
100 / 100
 575 ms 75640 KB 
#include "swap.h"
#include <bits/stdc++.h>
#include <vector>

#pragma gcc optimize("unroll-loops")
#pragma gcc optimize("o3")
#pragma gcc optimize("Ofast")

using namespace std;

const int N = 1e5 + 5;
const int infi = INT_MAX;

typedef pair<int, int> pii;

#define mp make_pair
#define sz(x) (int)x.size()
#define pb push_back
#define F first
#define S second

struct dsu{
    int pw[N];
    vector<pii> p[N], cnt1[N], cnt2[N], sz[N];
    vector<int> st[N];

    dsu(int n){
        for(int i = 1; i <= n; i++){
            st[i] = {i};
            p[i] = {{-1, i}};
            sz[i] = {{-1, 1}};
            cnt1[i] = {{-1, 0}};
            cnt2[i] = {{-1, 0}};
            pw[i] = 0;
        }
    }
    dsu(){

    }

    int getp(int v, int t){
        int pos = (--upper_bound(p[v].begin(), p[v].end(),mp(t, infi))) - p[v].begin();
        return p[v][pos].S;
    }

    void upd(int v, int nw, int t){
        if(nw == 1)
            cnt1[v].pb({t, cnt1[v].back().S - 1});
        if(nw == 2)
            cnt2[v].pb({t, cnt2[v].back().S - 1});
        if(nw == 0)
            cnt1[v].pb({t, cnt1[v].back().S + 1});
        if(nw == 1)
            cnt2[v].pb({t, cnt2[v].back().S + 1});
    }

    void uni(int a, int b, int t){
        int n1 = pw[a];
        int n2 = pw[b];
        //cout << n1 << ' ' << n2 << '\n';
        pw[a]++;
        pw[b]++;
        a = getp(a, t);
        b = getp(b, t);
        if(a == b){
            upd(a, n1, t);
            upd(a, n2, t);
            return;
        }
        if(sz(st[a]) > sz(st[b]))
            swap(a, b);
        sz[b].pb({t, sz[b].back().S + sz[a].back().S});
        for(auto e : st[a]){
            st[b].pb(e);
            p[e].pb({t, b});
            if(sz(p[e]) > 25)
                return;
        }
        st[a].clear();
        cnt1[b].pb({t, cnt1[a].back().S + cnt1[b].back().S});
        cnt2[b].pb({t, cnt2[a].back().S + cnt2[b].back().S});
        upd(b, n1, t);
        upd(b, n2, t);
    }
};

int n, m;
vector<pair<int, pair<int, int>>> edges;
dsu ds;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;
    for(int i = 0; i < m; i++){
        U[i]++;
        V[i]++;
        edges.pb({W[i], {V[i], U[i]}});
    }
    sort(edges.begin(), edges.end());
    ds = dsu(n);
    for(int i = 0; i < m; i++){
        ds.uni(edges[i].S.F, edges[i].S.S, i);
        /*cout << "comp: ";
        for(int j = 1; j <= n; j++){
            cout << ds.getp(j, infi) << ' ';
        }
        cout << '\n';
        cout << "cnt1: ";
        for(int i = 1; i <= n; i++){
            cout << ds.cnt1[ds.getp(i, infi)].back().S << ' ';
        }
        cout << '\n';
        cout << "cnt2: ";
        for(int i = 1; i <= n; i++){
            cout << ds.cnt2[ds.getp(i, infi)].back().S << ' ';
        }
        cout << '\n';*/
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;
    int lo = -1, hi = m;
    while(lo + 1 < hi){
        int m = (lo + hi) / 2;
        int x = ds.getp(X, m), y = ds.getp(Y, m);
        if(x != y){
            lo = m;
            continue;
        }
        int c1 = (--upper_bound(ds.cnt1[x].begin(), ds.cnt1[x].end(),mp(m, infi)))->S;
        int c2 = (--upper_bound(ds.cnt2[x].begin(), ds.cnt2[x].end(),mp(m, infi)))->S;
        int sz = (--upper_bound(ds.sz[x].begin(), ds.sz[x].end(),mp(m, infi)))->S;
        if(c1 == 2 && c2 == sz - 2){
            lo = m;
            continue;
        }
        hi = m;
    }
    if(hi == m)
        return -1;
    return edges[hi].F;
}

Compilation message

swap.cpp:5: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    5 | #pragma gcc optimize("unroll-loops")
      | 
swap.cpp:6: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    6 | #pragma gcc optimize("o3")
      | 
swap.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      |

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 10 ms 24668 KB Output is correct
3 Correct 10 ms 24664 KB Output is correct
4 Correct 11 ms 24784 KB Output is correct
5 Correct 12 ms 24884 KB Output is correct
6 Correct 11 ms 24924 KB Output is correct
7 Correct 12 ms 24912 KB Output is correct
8 Correct 11 ms 24924 KB Output is correct
9 Correct 130 ms 53924 KB Output is correct
10 Correct 184 ms 60020 KB Output is correct
11 Correct 182 ms 59328 KB Output is correct
12 Correct 208 ms 61380 KB Output is correct
13 Correct 117 ms 51732 KB Output is correct
14 Correct 168 ms 53628 KB Output is correct
15 Correct 294 ms 62288 KB Output is correct
16 Correct 283 ms 61796 KB Output is correct
17 Correct 298 ms 63904 KB Output is correct
18 Correct 335 ms 54040 KB Output is correct
19 Correct 116 ms 33816 KB Output is correct
20 Correct 282 ms 64064 KB Output is correct
21 Correct 315 ms 62804 KB Output is correct
22 Correct 316 ms 65384 KB Output is correct
23 Correct 316 ms 55604 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 10 ms 24668 KB Output is correct
3 Correct 428 ms 49408 KB Output is correct
4 Correct 412 ms 51104 KB Output is correct
5 Correct 457 ms 50568 KB Output is correct
6 Correct 405 ms 50984 KB Output is correct
7 Correct 429 ms 50744 KB Output is correct
8 Correct 428 ms 49864 KB Output is correct
9 Correct 418 ms 50492 KB Output is correct
10 Correct 418 ms 49784 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 10 ms 24668 KB Output is correct
3 Correct 10 ms 24664 KB Output is correct
4 Correct 11 ms 24784 KB Output is correct
5 Correct 12 ms 24884 KB Output is correct
6 Correct 11 ms 24924 KB Output is correct
7 Correct 12 ms 24912 KB Output is correct
8 Correct 11 ms 24924 KB Output is correct
9 Correct 10 ms 24668 KB Output is correct
10 Correct 11 ms 24924 KB Output is correct
11 Correct 11 ms 24924 KB Output is correct
12 Correct 11 ms 24924 KB Output is correct
13 Correct 10 ms 24848 KB Output is correct
14 Correct 12 ms 24924 KB Output is correct
15 Correct 11 ms 24924 KB Output is correct
16 Correct 11 ms 24980 KB Output is correct
17 Correct 11 ms 24920 KB Output is correct
18 Correct 11 ms 24888 KB Output is correct
19 Correct 11 ms 24924 KB Output is correct
20 Correct 11 ms 24924 KB Output is correct
21 Correct 11 ms 24984 KB Output is correct
22 Correct 10 ms 24668 KB Output is correct
23 Correct 11 ms 24756 KB Output is correct
24 Correct 11 ms 24924 KB Output is correct
25 Correct 12 ms 24960 KB Output is correct
26 Correct 11 ms 24924 KB Output is correct
27 Correct 14 ms 24832 KB Output is correct
28 Correct 16 ms 24924 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24668 KB Output is correct
2 Correct 11 ms 24668 KB Output is correct
3 Correct 10 ms 24668 KB Output is correct
4 Correct 10 ms 24664 KB Output is correct
5 Correct 11 ms 24784 KB Output is correct
6 Correct 12 ms 24884 KB Output is correct
7 Correct 11 ms 24924 KB Output is correct
8 Correct 12 ms 24912 KB Output is correct
9 Correct 11 ms 24924 KB Output is correct
10 Correct 130 ms 53924 KB Output is correct
11 Correct 184 ms 60020 KB Output is correct
12 Correct 182 ms 59328 KB Output is correct
13 Correct 208 ms 61380 KB Output is correct
14 Correct 117 ms 51732 KB Output is correct
15 Correct 11 ms 24924 KB Output is correct
16 Correct 11 ms 24924 KB Output is correct
17 Correct 11 ms 24924 KB Output is correct
18 Correct 10 ms 24848 KB Output is correct
19 Correct 12 ms 24924 KB Output is correct
20 Correct 11 ms 24924 KB Output is correct
21 Correct 11 ms 24980 KB Output is correct
22 Correct 11 ms 24920 KB Output is correct
23 Correct 11 ms 24888 KB Output is correct
24 Correct 11 ms 24924 KB Output is correct
25 Correct 11 ms 24924 KB Output is correct
26 Correct 11 ms 24984 KB Output is correct
27 Correct 10 ms 24668 KB Output is correct
28 Correct 11 ms 24756 KB Output is correct
29 Correct 11 ms 24924 KB Output is correct
30 Correct 12 ms 24960 KB Output is correct
31 Correct 11 ms 24924 KB Output is correct
32 Correct 14 ms 24832 KB Output is correct
33 Correct 16 ms 24924 KB Output is correct
34 Correct 22 ms 28952 KB Output is correct
35 Correct 154 ms 61380 KB Output is correct
36 Correct 153 ms 61124 KB Output is correct
37 Correct 176 ms 60536 KB Output is correct
38 Correct 145 ms 59328 KB Output is correct
39 Correct 165 ms 59076 KB Output is correct
40 Correct 115 ms 55492 KB Output is correct
41 Correct 155 ms 61892 KB Output is correct
42 Correct 154 ms 61892 KB Output is correct
43 Correct 102 ms 53256 KB Output is correct
44 Correct 133 ms 60616 KB Output is correct
45 Correct 123 ms 55956 KB Output is correct
46 Correct 144 ms 62868 KB Output is correct
47 Correct 131 ms 59080 KB Output is correct
48 Correct 116 ms 56572 KB Output is correct
49 Correct 60 ms 34716 KB Output is correct
50 Correct 48 ms 33276 KB Output is correct
51 Correct 94 ms 49864 KB Output is correct
52 Correct 170 ms 67264 KB Output is correct
53 Correct 175 ms 63724 KB Output is correct
54 Correct 207 ms 70852 KB Output is correct
55 Correct 95 ms 53188 KB Output is correct
56 Correct 143 ms 62400 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 10 ms 24668 KB Output is correct
3 Correct 10 ms 24664 KB Output is correct
4 Correct 11 ms 24784 KB Output is correct
5 Correct 12 ms 24884 KB Output is correct
6 Correct 11 ms 24924 KB Output is correct
7 Correct 12 ms 24912 KB Output is correct
8 Correct 11 ms 24924 KB Output is correct
9 Correct 130 ms 53924 KB Output is correct
10 Correct 184 ms 60020 KB Output is correct
11 Correct 182 ms 59328 KB Output is correct
12 Correct 208 ms 61380 KB Output is correct
13 Correct 117 ms 51732 KB Output is correct
14 Correct 168 ms 53628 KB Output is correct
15 Correct 294 ms 62288 KB Output is correct
16 Correct 283 ms 61796 KB Output is correct
17 Correct 298 ms 63904 KB Output is correct
18 Correct 335 ms 54040 KB Output is correct
19 Correct 428 ms 49408 KB Output is correct
20 Correct 412 ms 51104 KB Output is correct
21 Correct 457 ms 50568 KB Output is correct
22 Correct 405 ms 50984 KB Output is correct
23 Correct 429 ms 50744 KB Output is correct
24 Correct 428 ms 49864 KB Output is correct
25 Correct 418 ms 50492 KB Output is correct
26 Correct 418 ms 49784 KB Output is correct
27 Correct 11 ms 24924 KB Output is correct
28 Correct 11 ms 24924 KB Output is correct
29 Correct 11 ms 24924 KB Output is correct
30 Correct 10 ms 24848 KB Output is correct
31 Correct 12 ms 24924 KB Output is correct
32 Correct 11 ms 24924 KB Output is correct
33 Correct 11 ms 24980 KB Output is correct
34 Correct 11 ms 24920 KB Output is correct
35 Correct 11 ms 24888 KB Output is correct
36 Correct 22 ms 28952 KB Output is correct
37 Correct 154 ms 61380 KB Output is correct
38 Correct 153 ms 61124 KB Output is correct
39 Correct 176 ms 60536 KB Output is correct
40 Correct 145 ms 59328 KB Output is correct
41 Correct 165 ms 59076 KB Output is correct
42 Correct 115 ms 55492 KB Output is correct
43 Correct 155 ms 61892 KB Output is correct
44 Correct 154 ms 61892 KB Output is correct
45 Correct 102 ms 53256 KB Output is correct
46 Correct 133 ms 60616 KB Output is correct
47 Correct 33 ms 29456 KB Output is correct
48 Correct 277 ms 68160 KB Output is correct
49 Correct 273 ms 67376 KB Output is correct
50 Correct 277 ms 67328 KB Output is correct
51 Correct 263 ms 66696 KB Output is correct
52 Correct 298 ms 63692 KB Output is correct
53 Correct 226 ms 54200 KB Output is correct
54 Correct 317 ms 68904 KB Output is correct
55 Correct 270 ms 68908 KB Output is correct
56 Correct 361 ms 58568 KB Output is correct
57 Correct 286 ms 65836 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24668 KB Output is correct
2 Correct 11 ms 24668 KB Output is correct
3 Correct 10 ms 24668 KB Output is correct
4 Correct 10 ms 24664 KB Output is correct
5 Correct 11 ms 24784 KB Output is correct
6 Correct 12 ms 24884 KB Output is correct
7 Correct 11 ms 24924 KB Output is correct
8 Correct 12 ms 24912 KB Output is correct
9 Correct 11 ms 24924 KB Output is correct
10 Correct 130 ms 53924 KB Output is correct
11 Correct 184 ms 60020 KB Output is correct
12 Correct 182 ms 59328 KB Output is correct
13 Correct 208 ms 61380 KB Output is correct
14 Correct 117 ms 51732 KB Output is correct
15 Correct 168 ms 53628 KB Output is correct
16 Correct 294 ms 62288 KB Output is correct
17 Correct 283 ms 61796 KB Output is correct
18 Correct 298 ms 63904 KB Output is correct
19 Correct 335 ms 54040 KB Output is correct
20 Correct 428 ms 49408 KB Output is correct
21 Correct 412 ms 51104 KB Output is correct
22 Correct 457 ms 50568 KB Output is correct
23 Correct 405 ms 50984 KB Output is correct
24 Correct 429 ms 50744 KB Output is correct
25 Correct 428 ms 49864 KB Output is correct
26 Correct 418 ms 50492 KB Output is correct
27 Correct 418 ms 49784 KB Output is correct
28 Correct 11 ms 24924 KB Output is correct
29 Correct 11 ms 24924 KB Output is correct
30 Correct 11 ms 24924 KB Output is correct
31 Correct 10 ms 24848 KB Output is correct
32 Correct 12 ms 24924 KB Output is correct
33 Correct 11 ms 24924 KB Output is correct
34 Correct 11 ms 24980 KB Output is correct
35 Correct 11 ms 24920 KB Output is correct
36 Correct 11 ms 24888 KB Output is correct
37 Correct 22 ms 28952 KB Output is correct
38 Correct 154 ms 61380 KB Output is correct
39 Correct 153 ms 61124 KB Output is correct
40 Correct 176 ms 60536 KB Output is correct
41 Correct 145 ms 59328 KB Output is correct
42 Correct 165 ms 59076 KB Output is correct
43 Correct 115 ms 55492 KB Output is correct
44 Correct 155 ms 61892 KB Output is correct
45 Correct 154 ms 61892 KB Output is correct
46 Correct 102 ms 53256 KB Output is correct
47 Correct 133 ms 60616 KB Output is correct
48 Correct 33 ms 29456 KB Output is correct
49 Correct 277 ms 68160 KB Output is correct
50 Correct 273 ms 67376 KB Output is correct
51 Correct 277 ms 67328 KB Output is correct
52 Correct 263 ms 66696 KB Output is correct
53 Correct 298 ms 63692 KB Output is correct
54 Correct 226 ms 54200 KB Output is correct
55 Correct 317 ms 68904 KB Output is correct
56 Correct 270 ms 68908 KB Output is correct
57 Correct 361 ms 58568 KB Output is correct
58 Correct 286 ms 65836 KB Output is correct
59 Correct 116 ms 33816 KB Output is correct
60 Correct 282 ms 64064 KB Output is correct
61 Correct 315 ms 62804 KB Output is correct
62 Correct 316 ms 65384 KB Output is correct
63 Correct 316 ms 55604 KB Output is correct
64 Correct 11 ms 24924 KB Output is correct
65 Correct 11 ms 24924 KB Output is correct
66 Correct 11 ms 24984 KB Output is correct
67 Correct 10 ms 24668 KB Output is correct
68 Correct 11 ms 24756 KB Output is correct
69 Correct 11 ms 24924 KB Output is correct
70 Correct 12 ms 24960 KB Output is correct
71 Correct 11 ms 24924 KB Output is correct
72 Correct 14 ms 24832 KB Output is correct
73 Correct 16 ms 24924 KB Output is correct
74 Correct 123 ms 55956 KB Output is correct
75 Correct 144 ms 62868 KB Output is correct
76 Correct 131 ms 59080 KB Output is correct
77 Correct 116 ms 56572 KB Output is correct
78 Correct 60 ms 34716 KB Output is correct
79 Correct 48 ms 33276 KB Output is correct
80 Correct 94 ms 49864 KB Output is correct
81 Correct 170 ms 67264 KB Output is correct
82 Correct 175 ms 63724 KB Output is correct
83 Correct 207 ms 70852 KB Output is correct
84 Correct 95 ms 53188 KB Output is correct
85 Correct 143 ms 62400 KB Output is correct
86 Correct 127 ms 36716 KB Output is correct
87 Correct 288 ms 67116 KB Output is correct
88 Correct 278 ms 67116 KB Output is correct
89 Correct 500 ms 59368 KB Output is correct
90 Correct 287 ms 38908 KB Output is correct
91 Correct 365 ms 40784 KB Output is correct
92 Correct 509 ms 53852 KB Output is correct
93 Correct 401 ms 71096 KB Output is correct
94 Correct 498 ms 68260 KB Output is correct
95 Correct 318 ms 75640 KB Output is correct
96 Correct 384 ms 58468 KB Output is correct
97 Correct 575 ms 64896 KB Output is correct