oj.uz

Submission #571165

# Submission time Handle Problem Language Result Execution time Memory
571165 2022-06-01T11:18:01 Z SlavicG Swapping Cities (APIO20_swap) C++17
100 / 100
 670 ms 84440 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 4e5 + 10, K = 25;
vector<int> adj[N], g[N];
int val[N], degree[N], depth[N], jump[N][K], id, n;
bool vis[N], good;


struct DSU {
    vector<int> par;
    DSU() {
        par.assign(N, 0);
        forn(i, N) par[i] = i;
    }
    int get(int a) {
        return par[a] = (par[a] == a ? a : get(par[a]));
    }
    void uni(int a, int b) {
        a = get(a);
        b = get(b);
        par[a] = b;
    }
};
vector<int> component;

void get_component(int u) {
    vis[u] = true;
    component.pb(u);
    for(int v: g[u]) {
        if(!vis[v]) get_component(v);
    }
}

void dfs(int u, int par) {
    jump[u][0] = par;
    for(int v: adj[u]) {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int LCA(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);

    for(int j = K - 1; j >= 0; --j) {
        if(depth[jump[u][j]] >= depth[v]) {
            u = jump[u][j];
        }
    }
    //cout << u << ' ' << v << ' ' << depth[u] << ' ' << depth[v] << endl;
    if(u == v) return u;
    for(int j = K - 1; j >= 0; --j) {
        if(jump[u][j] != jump[v][j]) {
            u = jump[u][j], v = jump[v][j];
        }
    }
    //cout << u << ' ' << jump[u][0] << endl;
    return jump[u][0];
}

void init(int _n, int m, vector<int> U, vector<int> V, vector<int> W) {
    n = _n;
    id = n;

    vector<array<int, 3>> edges;
    DSU d;
    DSU connect;
    for(int i = 0; i < m; ++i) {
        edges.pb({W[i], U[i], V[i]});
    }
    sort(all(edges));
    
    for(auto x: edges) {
        int u = x[1], v = x[2], w = x[0];
        
        g[u].pb(v);
        g[v].pb(u);

        if(d.get(u) == d.get(v)) continue;
        if(d.get(u) == u) swap(u, v);

        if(d.get(u) != u && d.get(v) != v) {
            adj[id].pb(d.get(u));
            adj[id].pb(d.get(v));
            d.uni(u, id);
            d.uni(v, id);
            val[id] = w;
            ++id;
        } else if(d.get(u) != u) {
            component.clear();
            get_component(v);
            for(auto x: component) {
                adj[id].pb(x);
                d.uni(x, id);
            }
            val[id] = w;
            ++id;

            adj[id].pb(d.get(u));
            adj[id].pb(d.get(v));
            d.uni(u, id);
            d.uni(v, id);
            val[id] = w;
            ++id;
        } else {
            ++degree[u];
            ++degree[v];
            if(connect.get(u) == connect.get(v) || degree[u] > 2 || degree[v] > 2) {
                component.clear();
                get_component(u);
                good = true;
                for(auto x: component) {
                    d.uni(x, id);
                    adj[id].pb(x);
                }
                
                val[id] = w;
                ++id;
            } else{
                connect.uni(u, v);
            }

        }
    }
    
    dfs(id - 1, id - 1);
    for(int k = 1; k < K; ++k) {
        for(int i = 0; i < N; ++i) {
            jump[i][k] = id - 1;
        }
    }

    for(int k = 1; k < K; ++k) {
        for(int i = 0; i < N; ++i) {
            jump[i][k] = jump[jump[i][k - 1]][k - 1];
        }
    }

    
}

int getMinimumFuelCapacity(int u, int v) {
    if(!good) return -1;
    return val[LCA(u, v)];
}

/*
void solve() {  
    int NN, m; cin >> NN >> m;
    vector<int> a(m), b(m), c(m);
    forn(i, m) cin >> a[i];
    forn(i, m) cin >> b[i];
    forn(i, m) cin >> c[i];
    init(NN, m, a, b, c);
    cout << getMinimumFuelCapacity(1, 2) << "\n";
    cout << getMinimumFuelCapacity(2, 4) << "\n";
    cout << getMinimumFuelCapacity(0, 1) << "\n";
    
}   
     
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 61268 KB Output is correct
2 Correct 160 ms 61388 KB Output is correct
3 Correct 169 ms 61468 KB Output is correct
4 Correct 160 ms 61324 KB Output is correct
5 Correct 164 ms 61428 KB Output is correct
6 Correct 166 ms 61432 KB Output is correct
7 Correct 164 ms 61360 KB Output is correct
8 Correct 160 ms 61440 KB Output is correct
9 Correct 206 ms 66916 KB Output is correct
10 Correct 229 ms 68204 KB Output is correct
11 Correct 237 ms 67940 KB Output is correct
12 Correct 247 ms 68388 KB Output is correct
13 Correct 226 ms 68684 KB Output is correct
14 Correct 231 ms 67104 KB Output is correct
15 Correct 274 ms 69872 KB Output is correct
16 Correct 274 ms 69616 KB Output is correct
17 Correct 292 ms 69952 KB Output is correct
18 Correct 268 ms 70336 KB Output is correct
19 Correct 260 ms 64756 KB Output is correct
20 Correct 344 ms 75920 KB Output is correct
21 Correct 384 ms 75496 KB Output is correct
22 Correct 403 ms 76480 KB Output is correct
23 Correct 359 ms 76596 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 61268 KB Output is correct
2 Correct 160 ms 61388 KB Output is correct
3 Correct 605 ms 83416 KB Output is correct
4 Correct 636 ms 84440 KB Output is correct
5 Correct 622 ms 83744 KB Output is correct
6 Correct 588 ms 84288 KB Output is correct
7 Correct 614 ms 83984 KB Output is correct
8 Correct 599 ms 83176 KB Output is correct
9 Correct 617 ms 83916 KB Output is correct
10 Correct 603 ms 82956 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 61268 KB Output is correct
2 Correct 160 ms 61388 KB Output is correct
3 Correct 169 ms 61468 KB Output is correct
4 Correct 160 ms 61324 KB Output is correct
5 Correct 164 ms 61428 KB Output is correct
6 Correct 166 ms 61432 KB Output is correct
7 Correct 164 ms 61360 KB Output is correct
8 Correct 160 ms 61440 KB Output is correct
9 Correct 173 ms 61260 KB Output is correct
10 Correct 168 ms 61476 KB Output is correct
11 Correct 166 ms 61396 KB Output is correct
12 Correct 196 ms 61464 KB Output is correct
13 Correct 183 ms 61476 KB Output is correct
14 Correct 173 ms 61476 KB Output is correct
15 Correct 168 ms 61488 KB Output is correct
16 Correct 184 ms 61492 KB Output is correct
17 Correct 172 ms 61560 KB Output is correct
18 Correct 164 ms 61496 KB Output is correct
19 Correct 167 ms 61388 KB Output is correct
20 Correct 165 ms 61476 KB Output is correct
21 Correct 175 ms 61604 KB Output is correct
22 Correct 170 ms 61436 KB Output is correct
23 Correct 171 ms 61396 KB Output is correct
24 Correct 167 ms 61492 KB Output is correct
25 Correct 171 ms 61648 KB Output is correct
26 Correct 198 ms 61476 KB Output is correct
27 Correct 162 ms 61556 KB Output is correct
28 Correct 185 ms 61696 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 61260 KB Output is correct
2 Correct 163 ms 61268 KB Output is correct
3 Correct 160 ms 61388 KB Output is correct
4 Correct 169 ms 61468 KB Output is correct
5 Correct 160 ms 61324 KB Output is correct
6 Correct 164 ms 61428 KB Output is correct
7 Correct 166 ms 61432 KB Output is correct
8 Correct 164 ms 61360 KB Output is correct
9 Correct 160 ms 61440 KB Output is correct
10 Correct 206 ms 66916 KB Output is correct
11 Correct 229 ms 68204 KB Output is correct
12 Correct 237 ms 67940 KB Output is correct
13 Correct 247 ms 68388 KB Output is correct
14 Correct 226 ms 68684 KB Output is correct
15 Correct 168 ms 61476 KB Output is correct
16 Correct 166 ms 61396 KB Output is correct
17 Correct 196 ms 61464 KB Output is correct
18 Correct 183 ms 61476 KB Output is correct
19 Correct 173 ms 61476 KB Output is correct
20 Correct 168 ms 61488 KB Output is correct
21 Correct 184 ms 61492 KB Output is correct
22 Correct 172 ms 61560 KB Output is correct
23 Correct 164 ms 61496 KB Output is correct
24 Correct 167 ms 61388 KB Output is correct
25 Correct 165 ms 61476 KB Output is correct
26 Correct 175 ms 61604 KB Output is correct
27 Correct 170 ms 61436 KB Output is correct
28 Correct 171 ms 61396 KB Output is correct
29 Correct 167 ms 61492 KB Output is correct
30 Correct 171 ms 61648 KB Output is correct
31 Correct 198 ms 61476 KB Output is correct
32 Correct 162 ms 61556 KB Output is correct
33 Correct 185 ms 61696 KB Output is correct
34 Correct 179 ms 63048 KB Output is correct
35 Correct 279 ms 71376 KB Output is correct
36 Correct 278 ms 71280 KB Output is correct
37 Correct 262 ms 70800 KB Output is correct
38 Correct 266 ms 71016 KB Output is correct
39 Correct 277 ms 71620 KB Output is correct
40 Correct 268 ms 71808 KB Output is correct
41 Correct 268 ms 72752 KB Output is correct
42 Correct 245 ms 73744 KB Output is correct
43 Correct 273 ms 81772 KB Output is correct
44 Correct 292 ms 73408 KB Output is correct
45 Correct 309 ms 76084 KB Output is correct
46 Correct 287 ms 71216 KB Output is correct
47 Correct 283 ms 71240 KB Output is correct
48 Correct 297 ms 75956 KB Output is correct
49 Correct 244 ms 70784 KB Output is correct
50 Correct 226 ms 69452 KB Output is correct
51 Correct 289 ms 74380 KB Output is correct
52 Correct 332 ms 74548 KB Output is correct
53 Correct 340 ms 77200 KB Output is correct
54 Correct 331 ms 77840 KB Output is correct
55 Correct 278 ms 81296 KB Output is correct
56 Correct 359 ms 78936 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 61268 KB Output is correct
2 Correct 160 ms 61388 KB Output is correct
3 Correct 169 ms 61468 KB Output is correct
4 Correct 160 ms 61324 KB Output is correct
5 Correct 164 ms 61428 KB Output is correct
6 Correct 166 ms 61432 KB Output is correct
7 Correct 164 ms 61360 KB Output is correct
8 Correct 160 ms 61440 KB Output is correct
9 Correct 206 ms 66916 KB Output is correct
10 Correct 229 ms 68204 KB Output is correct
11 Correct 237 ms 67940 KB Output is correct
12 Correct 247 ms 68388 KB Output is correct
13 Correct 226 ms 68684 KB Output is correct
14 Correct 231 ms 67104 KB Output is correct
15 Correct 274 ms 69872 KB Output is correct
16 Correct 274 ms 69616 KB Output is correct
17 Correct 292 ms 69952 KB Output is correct
18 Correct 268 ms 70336 KB Output is correct
19 Correct 605 ms 83416 KB Output is correct
20 Correct 636 ms 84440 KB Output is correct
21 Correct 622 ms 83744 KB Output is correct
22 Correct 588 ms 84288 KB Output is correct
23 Correct 614 ms 83984 KB Output is correct
24 Correct 599 ms 83176 KB Output is correct
25 Correct 617 ms 83916 KB Output is correct
26 Correct 603 ms 82956 KB Output is correct
27 Correct 168 ms 61476 KB Output is correct
28 Correct 166 ms 61396 KB Output is correct
29 Correct 196 ms 61464 KB Output is correct
30 Correct 183 ms 61476 KB Output is correct
31 Correct 173 ms 61476 KB Output is correct
32 Correct 168 ms 61488 KB Output is correct
33 Correct 184 ms 61492 KB Output is correct
34 Correct 172 ms 61560 KB Output is correct
35 Correct 164 ms 61496 KB Output is correct
36 Correct 179 ms 63048 KB Output is correct
37 Correct 279 ms 71376 KB Output is correct
38 Correct 278 ms 71280 KB Output is correct
39 Correct 262 ms 70800 KB Output is correct
40 Correct 266 ms 71016 KB Output is correct
41 Correct 277 ms 71620 KB Output is correct
42 Correct 268 ms 71808 KB Output is correct
43 Correct 268 ms 72752 KB Output is correct
44 Correct 245 ms 73744 KB Output is correct
45 Correct 273 ms 81772 KB Output is correct
46 Correct 292 ms 73408 KB Output is correct
47 Correct 222 ms 63316 KB Output is correct
48 Correct 399 ms 74488 KB Output is correct
49 Correct 397 ms 72640 KB Output is correct
50 Correct 400 ms 72512 KB Output is correct
51 Correct 403 ms 72656 KB Output is correct
52 Correct 425 ms 72768 KB Output is correct
53 Correct 399 ms 71508 KB Output is correct
54 Correct 404 ms 74176 KB Output is correct
55 Correct 381 ms 74864 KB Output is correct
56 Correct 670 ms 82708 KB Output is correct
57 Correct 463 ms 75108 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 61260 KB Output is correct
2 Correct 163 ms 61268 KB Output is correct
3 Correct 160 ms 61388 KB Output is correct
4 Correct 169 ms 61468 KB Output is correct
5 Correct 160 ms 61324 KB Output is correct
6 Correct 164 ms 61428 KB Output is correct
7 Correct 166 ms 61432 KB Output is correct
8 Correct 164 ms 61360 KB Output is correct
9 Correct 160 ms 61440 KB Output is correct
10 Correct 206 ms 66916 KB Output is correct
11 Correct 229 ms 68204 KB Output is correct
12 Correct 237 ms 67940 KB Output is correct
13 Correct 247 ms 68388 KB Output is correct
14 Correct 226 ms 68684 KB Output is correct
15 Correct 231 ms 67104 KB Output is correct
16 Correct 274 ms 69872 KB Output is correct
17 Correct 274 ms 69616 KB Output is correct
18 Correct 292 ms 69952 KB Output is correct
19 Correct 268 ms 70336 KB Output is correct
20 Correct 605 ms 83416 KB Output is correct
21 Correct 636 ms 84440 KB Output is correct
22 Correct 622 ms 83744 KB Output is correct
23 Correct 588 ms 84288 KB Output is correct
24 Correct 614 ms 83984 KB Output is correct
25 Correct 599 ms 83176 KB Output is correct
26 Correct 617 ms 83916 KB Output is correct
27 Correct 603 ms 82956 KB Output is correct
28 Correct 168 ms 61476 KB Output is correct
29 Correct 166 ms 61396 KB Output is correct
30 Correct 196 ms 61464 KB Output is correct
31 Correct 183 ms 61476 KB Output is correct
32 Correct 173 ms 61476 KB Output is correct
33 Correct 168 ms 61488 KB Output is correct
34 Correct 184 ms 61492 KB Output is correct
35 Correct 172 ms 61560 KB Output is correct
36 Correct 164 ms 61496 KB Output is correct
37 Correct 179 ms 63048 KB Output is correct
38 Correct 279 ms 71376 KB Output is correct
39 Correct 278 ms 71280 KB Output is correct
40 Correct 262 ms 70800 KB Output is correct
41 Correct 266 ms 71016 KB Output is correct
42 Correct 277 ms 71620 KB Output is correct
43 Correct 268 ms 71808 KB Output is correct
44 Correct 268 ms 72752 KB Output is correct
45 Correct 245 ms 73744 KB Output is correct
46 Correct 273 ms 81772 KB Output is correct
47 Correct 292 ms 73408 KB Output is correct
48 Correct 222 ms 63316 KB Output is correct
49 Correct 399 ms 74488 KB Output is correct
50 Correct 397 ms 72640 KB Output is correct
51 Correct 400 ms 72512 KB Output is correct
52 Correct 403 ms 72656 KB Output is correct
53 Correct 425 ms 72768 KB Output is correct
54 Correct 399 ms 71508 KB Output is correct
55 Correct 404 ms 74176 KB Output is correct
56 Correct 381 ms 74864 KB Output is correct
57 Correct 670 ms 82708 KB Output is correct
58 Correct 463 ms 75108 KB Output is correct
59 Correct 260 ms 64756 KB Output is correct
60 Correct 344 ms 75920 KB Output is correct
61 Correct 384 ms 75496 KB Output is correct
62 Correct 403 ms 76480 KB Output is correct
63 Correct 359 ms 76596 KB Output is correct
64 Correct 167 ms 61388 KB Output is correct
65 Correct 165 ms 61476 KB Output is correct
66 Correct 175 ms 61604 KB Output is correct
67 Correct 170 ms 61436 KB Output is correct
68 Correct 171 ms 61396 KB Output is correct
69 Correct 167 ms 61492 KB Output is correct
70 Correct 171 ms 61648 KB Output is correct
71 Correct 198 ms 61476 KB Output is correct
72 Correct 162 ms 61556 KB Output is correct
73 Correct 185 ms 61696 KB Output is correct
74 Correct 309 ms 76084 KB Output is correct
75 Correct 287 ms 71216 KB Output is correct
76 Correct 283 ms 71240 KB Output is correct
77 Correct 297 ms 75956 KB Output is correct
78 Correct 244 ms 70784 KB Output is correct
79 Correct 226 ms 69452 KB Output is correct
80 Correct 289 ms 74380 KB Output is correct
81 Correct 332 ms 74548 KB Output is correct
82 Correct 340 ms 77200 KB Output is correct
83 Correct 331 ms 77840 KB Output is correct
84 Correct 278 ms 81296 KB Output is correct
85 Correct 359 ms 78936 KB Output is correct
86 Correct 260 ms 68032 KB Output is correct
87 Correct 431 ms 72484 KB Output is correct
88 Correct 372 ms 72456 KB Output is correct
89 Correct 476 ms 77204 KB Output is correct
90 Correct 351 ms 72404 KB Output is correct
91 Correct 367 ms 72532 KB Output is correct
92 Correct 516 ms 75320 KB Output is correct
93 Correct 396 ms 76040 KB Output is correct
94 Correct 454 ms 77884 KB Output is correct
95 Correct 448 ms 79444 KB Output is correct
96 Correct 631 ms 82700 KB Output is correct
97 Correct 562 ms 78524 KB Output is correct