oj.uz

Submission #1059817

# Submission time Handle Problem Language Result Execution time Memory
1059817 2024-08-15T08:26:37 Z mispertion Swapping Cities (APIO20_swap) C++17
50 / 100
 2000 ms 49848 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 pb push_back
#define F first
#define S second

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

    dsu(int n){
        for(int i = 1; i <= n; 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();
        int pr = p[v][pos].S;
        if(pr == v)
            return v;
        return getp(pr, t);
    }

    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[a] > sz[b])
            swap(a, b);
        p[a].pb({t, b});
        sz[b].pb({t, sz[a].back().S + sz[b].back().S});
        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 8 ms 19804 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 10 ms 20060 KB Output is correct
5 Correct 10 ms 20060 KB Output is correct
6 Correct 8 ms 20056 KB Output is correct
7 Correct 10 ms 20060 KB Output is correct
8 Correct 13 ms 20060 KB Output is correct
9 Correct 80 ms 38868 KB Output is correct
10 Correct 108 ms 42952 KB Output is correct
11 Correct 98 ms 42696 KB Output is correct
12 Correct 107 ms 43972 KB Output is correct
13 Correct 82 ms 43348 KB Output is correct
14 Correct 119 ms 38852 KB Output is correct
15 Correct 496 ms 45008 KB Output is correct
16 Correct 464 ms 44408 KB Output is correct
17 Correct 498 ms 45732 KB Output is correct
18 Correct 323 ms 44404 KB Output is correct
19 Correct 253 ms 27244 KB Output is correct
20 Correct 466 ms 46144 KB Output is correct
21 Correct 477 ms 45536 KB Output is correct
22 Correct 493 ms 47020 KB Output is correct
23 Correct 352 ms 44840 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19804 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 438 ms 41644 KB Output is correct
4 Correct 403 ms 42508 KB Output is correct
5 Correct 430 ms 41964 KB Output is correct
6 Correct 402 ms 42280 KB Output is correct
7 Correct 420 ms 42220 KB Output is correct
8 Correct 413 ms 41388 KB Output is correct
9 Correct 439 ms 42048 KB Output is correct
10 Correct 443 ms 41320 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19804 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 10 ms 20060 KB Output is correct
5 Correct 10 ms 20060 KB Output is correct
6 Correct 8 ms 20056 KB Output is correct
7 Correct 10 ms 20060 KB Output is correct
8 Correct 13 ms 20060 KB Output is correct
9 Correct 8 ms 19800 KB Output is correct
10 Correct 8 ms 20060 KB Output is correct
11 Correct 8 ms 20164 KB Output is correct
12 Correct 9 ms 20164 KB Output is correct
13 Correct 8 ms 20060 KB Output is correct
14 Correct 9 ms 20060 KB Output is correct
15 Correct 9 ms 20056 KB Output is correct
16 Correct 9 ms 20060 KB Output is correct
17 Correct 8 ms 20056 KB Output is correct
18 Correct 9 ms 20204 KB Output is correct
19 Correct 10 ms 20180 KB Output is correct
20 Correct 8 ms 20060 KB Output is correct
21 Correct 8 ms 20060 KB Output is correct
22 Correct 9 ms 19952 KB Output is correct
23 Correct 8 ms 20060 KB Output is correct
24 Correct 9 ms 20060 KB Output is correct
25 Correct 10 ms 20312 KB Output is correct
26 Correct 9 ms 20300 KB Output is correct
27 Correct 8 ms 20060 KB Output is correct
28 Correct 9 ms 20060 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19800 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 8 ms 19804 KB Output is correct
5 Correct 10 ms 20060 KB Output is correct
6 Correct 10 ms 20060 KB Output is correct
7 Correct 8 ms 20056 KB Output is correct
8 Correct 10 ms 20060 KB Output is correct
9 Correct 13 ms 20060 KB Output is correct
10 Correct 80 ms 38868 KB Output is correct
11 Correct 108 ms 42952 KB Output is correct
12 Correct 98 ms 42696 KB Output is correct
13 Correct 107 ms 43972 KB Output is correct
14 Correct 82 ms 43348 KB Output is correct
15 Correct 8 ms 20060 KB Output is correct
16 Correct 8 ms 20164 KB Output is correct
17 Correct 9 ms 20164 KB Output is correct
18 Correct 8 ms 20060 KB Output is correct
19 Correct 9 ms 20060 KB Output is correct
20 Correct 9 ms 20056 KB Output is correct
21 Correct 9 ms 20060 KB Output is correct
22 Correct 8 ms 20056 KB Output is correct
23 Correct 9 ms 20204 KB Output is correct
24 Correct 10 ms 20180 KB Output is correct
25 Correct 8 ms 20060 KB Output is correct
26 Correct 8 ms 20060 KB Output is correct
27 Correct 9 ms 19952 KB Output is correct
28 Correct 8 ms 20060 KB Output is correct
29 Correct 9 ms 20060 KB Output is correct
30 Correct 10 ms 20312 KB Output is correct
31 Correct 9 ms 20300 KB Output is correct
32 Correct 8 ms 20060 KB Output is correct
33 Correct 9 ms 20060 KB Output is correct
34 Correct 26 ms 23064 KB Output is correct
35 Correct 109 ms 43976 KB Output is correct
36 Correct 92 ms 43976 KB Output is correct
37 Correct 96 ms 43976 KB Output is correct
38 Correct 97 ms 43464 KB Output is correct
39 Correct 101 ms 43396 KB Output is correct
40 Correct 83 ms 41160 KB Output is correct
41 Correct 94 ms 43976 KB Output is correct
42 Correct 100 ms 43976 KB Output is correct
43 Correct 69 ms 42696 KB Output is correct
44 Correct 97 ms 43208 KB Output is correct
45 Correct 167 ms 41044 KB Output is correct
46 Correct 95 ms 43972 KB Output is correct
47 Correct 98 ms 43716 KB Output is correct
48 Correct 129 ms 43012 KB Output is correct
49 Correct 80 ms 28104 KB Output is correct
50 Correct 81 ms 25832 KB Output is correct
51 Correct 152 ms 37344 KB Output is correct
52 Correct 142 ms 48556 KB Output is correct
53 Correct 158 ms 49848 KB Output is correct
54 Correct 188 ms 49636 KB Output is correct
55 Correct 76 ms 42952 KB Output is correct
56 Correct 214 ms 46732 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19804 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 10 ms 20060 KB Output is correct
5 Correct 10 ms 20060 KB Output is correct
6 Correct 8 ms 20056 KB Output is correct
7 Correct 10 ms 20060 KB Output is correct
8 Correct 13 ms 20060 KB Output is correct
9 Correct 80 ms 38868 KB Output is correct
10 Correct 108 ms 42952 KB Output is correct
11 Correct 98 ms 42696 KB Output is correct
12 Correct 107 ms 43972 KB Output is correct
13 Correct 82 ms 43348 KB Output is correct
14 Correct 119 ms 38852 KB Output is correct
15 Correct 496 ms 45008 KB Output is correct
16 Correct 464 ms 44408 KB Output is correct
17 Correct 498 ms 45732 KB Output is correct
18 Correct 323 ms 44404 KB Output is correct
19 Correct 438 ms 41644 KB Output is correct
20 Correct 403 ms 42508 KB Output is correct
21 Correct 430 ms 41964 KB Output is correct
22 Correct 402 ms 42280 KB Output is correct
23 Correct 420 ms 42220 KB Output is correct
24 Correct 413 ms 41388 KB Output is correct
25 Correct 439 ms 42048 KB Output is correct
26 Correct 443 ms 41320 KB Output is correct
27 Correct 8 ms 20060 KB Output is correct
28 Correct 8 ms 20164 KB Output is correct
29 Correct 9 ms 20164 KB Output is correct
30 Correct 8 ms 20060 KB Output is correct
31 Correct 9 ms 20060 KB Output is correct
32 Correct 9 ms 20056 KB Output is correct
33 Correct 9 ms 20060 KB Output is correct
34 Correct 8 ms 20056 KB Output is correct
35 Correct 9 ms 20204 KB Output is correct
36 Correct 26 ms 23064 KB Output is correct
37 Correct 109 ms 43976 KB Output is correct
38 Correct 92 ms 43976 KB Output is correct
39 Correct 96 ms 43976 KB Output is correct
40 Correct 97 ms 43464 KB Output is correct
41 Correct 101 ms 43396 KB Output is correct
42 Correct 83 ms 41160 KB Output is correct
43 Correct 94 ms 43976 KB Output is correct
44 Correct 100 ms 43976 KB Output is correct
45 Correct 69 ms 42696 KB Output is correct
46 Correct 97 ms 43208 KB Output is correct
47 Correct 47 ms 23084 KB Output is correct
48 Correct 448 ms 46540 KB Output is correct
49 Correct 458 ms 46484 KB Output is correct
50 Correct 500 ms 46384 KB Output is correct
51 Correct 457 ms 46388 KB Output is correct
52 Correct 478 ms 44880 KB Output is correct
53 Correct 518 ms 38840 KB Output is correct
54 Correct 453 ms 47024 KB Output is correct
55 Correct 458 ms 46404 KB Output is correct
56 Execution timed out 2067 ms 44440 KB Time limit exceeded
57 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19800 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 8 ms 19804 KB Output is correct
5 Correct 10 ms 20060 KB Output is correct
6 Correct 10 ms 20060 KB Output is correct
7 Correct 8 ms 20056 KB Output is correct
8 Correct 10 ms 20060 KB Output is correct
9 Correct 13 ms 20060 KB Output is correct
10 Correct 80 ms 38868 KB Output is correct
11 Correct 108 ms 42952 KB Output is correct
12 Correct 98 ms 42696 KB Output is correct
13 Correct 107 ms 43972 KB Output is correct
14 Correct 82 ms 43348 KB Output is correct
15 Correct 119 ms 38852 KB Output is correct
16 Correct 496 ms 45008 KB Output is correct
17 Correct 464 ms 44408 KB Output is correct
18 Correct 498 ms 45732 KB Output is correct
19 Correct 323 ms 44404 KB Output is correct
20 Correct 438 ms 41644 KB Output is correct
21 Correct 403 ms 42508 KB Output is correct
22 Correct 430 ms 41964 KB Output is correct
23 Correct 402 ms 42280 KB Output is correct
24 Correct 420 ms 42220 KB Output is correct
25 Correct 413 ms 41388 KB Output is correct
26 Correct 439 ms 42048 KB Output is correct
27 Correct 443 ms 41320 KB Output is correct
28 Correct 8 ms 20060 KB Output is correct
29 Correct 8 ms 20164 KB Output is correct
30 Correct 9 ms 20164 KB Output is correct
31 Correct 8 ms 20060 KB Output is correct
32 Correct 9 ms 20060 KB Output is correct
33 Correct 9 ms 20056 KB Output is correct
34 Correct 9 ms 20060 KB Output is correct
35 Correct 8 ms 20056 KB Output is correct
36 Correct 9 ms 20204 KB Output is correct
37 Correct 26 ms 23064 KB Output is correct
38 Correct 109 ms 43976 KB Output is correct
39 Correct 92 ms 43976 KB Output is correct
40 Correct 96 ms 43976 KB Output is correct
41 Correct 97 ms 43464 KB Output is correct
42 Correct 101 ms 43396 KB Output is correct
43 Correct 83 ms 41160 KB Output is correct
44 Correct 94 ms 43976 KB Output is correct
45 Correct 100 ms 43976 KB Output is correct
46 Correct 69 ms 42696 KB Output is correct
47 Correct 97 ms 43208 KB Output is correct
48 Correct 47 ms 23084 KB Output is correct
49 Correct 448 ms 46540 KB Output is correct
50 Correct 458 ms 46484 KB Output is correct
51 Correct 500 ms 46384 KB Output is correct
52 Correct 457 ms 46388 KB Output is correct
53 Correct 478 ms 44880 KB Output is correct
54 Correct 518 ms 38840 KB Output is correct
55 Correct 453 ms 47024 KB Output is correct
56 Correct 458 ms 46404 KB Output is correct
57 Execution timed out 2067 ms 44440 KB Time limit exceeded
58 Halted 0 ms 0 KB -