oj.uz

Submission #717532

# Submission time Handle Problem Language Result Execution time Memory
717532 2023-04-02T06:15:14 Z alvingogo Swapping Cities (APIO20_swap) C++14
100 / 100
 404 ms 43376 KB 
#include <bits/stdc++.h>
#include "swap.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct TR{
    vector<vector<int> > e;
    vector<array<int,20> > as;
    vector<int> tag;
    vector<int> dep;
    vector<int> val;
    int sz=0;
    void init(int x){
        e.resize(x);
        as.resize(x);
        dep.resize(x,-1);
        val.resize(x,2e9);
        sz=x;
    }
    void add(int cnt){
        //cout << sz << " " << cnt << "\n";
        e.push_back(vector<int>());
        as.push_back(array<int,20>());
        dep.push_back(-1);
        val.push_back(cnt);
        sz++;
    }
    void eg(int a,int b){
        //cout << a << "e" << b << '\n';
        e[a].push_back(b);
    }
    void dfs(int r,int f){
        as[r][0]=f;
        val[r]=min(val[r],val[f]);
        dep[r]=dep[f]+1;
        for(int i=1;i<20;i++){
            as[r][i]=as[as[r][i-1]][i-1];
        }
        for(auto h:e[r]){
            dfs(h,r);
        }
    }
    int lca(int a,int b){
        if(dep[a]>dep[b]){
            swap(a,b);
        }
        for(int i=19;i>=0;i--){
            if(dep[as[b][i]]>=dep[a]){
                b=as[b][i];
            }
        }
        for(int i=19;i>=0;i--){
            if(as[b][i]!=as[a][i]){
                a=as[a][i];
                b=as[b][i];
            }
        }
        return as[a][0];
    }
}tr;

struct DSU{
    vector<int> bo,tag;
    int sz=0;
    vector<int> deg;
    void init(int n){
        bo.resize(n);
        iota(bo.begin(),bo.end(),0);
        tag.resize(n);
        deg.resize(n);
        sz=n;
    }
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    void merge(int x,int y,int cnt){
        deg[x]++;
        deg[y]++;
        int u=(deg[x]>=3 || deg[y]>=3);
        x=find(x);
        y=find(y);
        if(x==y){
            if(tag[x]==0){
                tag[x]=1;
                tr.val[x]=cnt;
            }
            return;
        }
        tag.push_back(0);
        bo.push_back(sz);
        deg.push_back(0);
        bo[x]=bo[y]=sz;
        tag[sz]|=tag[x];
        tag[sz]|=tag[y];
        tag[sz]|=u;
        if(!tag[sz]){
            cnt=2e9;
        }
        tr.add(cnt);
        tr.eg(sz,x);
        tr.eg(sz,y);
        sz++;
    }
}dsu;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    dsu.init(n);
    tr.init(n);
    vector<pair<int,pair<int,int> > > eg;
    for(int i=0;i<m;i++){
        eg.push_back({w[i],{u[i],v[i]}});
    }
    sort(eg.begin(),eg.end());
    for(auto h:eg){
        dsu.merge(h.sc.fs,h.sc.sc,h.fs);
    }
    tr.tag=dsu.tag;
    tr.dfs(tr.sz-1,tr.sz-1);
}

int getMinimumFuelCapacity(int x, int y) {
    int u=tr.lca(x,y);
    if(tr.val[u]>1.5e9){
        return -1;
    }
    return tr.val[u];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 93 ms 25208 KB Output is correct
10 Correct 115 ms 30644 KB Output is correct
11 Correct 116 ms 30248 KB Output is correct
12 Correct 132 ms 32100 KB Output is correct
13 Correct 122 ms 33492 KB Output is correct
14 Correct 105 ms 25268 KB Output is correct
15 Correct 238 ms 32544 KB Output is correct
16 Correct 249 ms 31600 KB Output is correct
17 Correct 251 ms 33624 KB Output is correct
18 Correct 361 ms 35084 KB Output is correct
19 Correct 93 ms 8584 KB Output is correct
20 Correct 234 ms 32852 KB Output is correct
21 Correct 259 ms 31916 KB Output is correct
22 Correct 258 ms 33936 KB Output is correct
23 Correct 404 ms 35476 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 275 ms 34980 KB Output is correct
4 Correct 272 ms 36548 KB Output is correct
5 Correct 290 ms 35624 KB Output is correct
6 Correct 305 ms 36308 KB Output is correct
7 Correct 327 ms 36112 KB Output is correct
8 Correct 281 ms 34732 KB Output is correct
9 Correct 296 ms 35832 KB Output is correct
10 Correct 303 ms 34536 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 572 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 1 ms 700 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 560 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 564 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 2 ms 696 KB Output is correct
25 Correct 2 ms 724 KB Output is correct
26 Correct 2 ms 736 KB Output is correct
27 Correct 1 ms 724 KB Output is correct
28 Correct 2 ms 724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 93 ms 25208 KB Output is correct
11 Correct 115 ms 30644 KB Output is correct
12 Correct 116 ms 30248 KB Output is correct
13 Correct 132 ms 32100 KB Output is correct
14 Correct 122 ms 33492 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 572 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 700 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 560 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 564 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 2 ms 696 KB Output is correct
30 Correct 2 ms 724 KB Output is correct
31 Correct 2 ms 736 KB Output is correct
32 Correct 1 ms 724 KB Output is correct
33 Correct 2 ms 724 KB Output is correct
34 Correct 11 ms 4904 KB Output is correct
35 Correct 117 ms 33844 KB Output is correct
36 Correct 126 ms 33768 KB Output is correct
37 Correct 116 ms 33712 KB Output is correct
38 Correct 116 ms 33240 KB Output is correct
39 Correct 127 ms 33196 KB Output is correct
40 Correct 106 ms 30364 KB Output is correct
41 Correct 122 ms 34124 KB Output is correct
42 Correct 113 ms 33748 KB Output is correct
43 Correct 103 ms 35776 KB Output is correct
44 Correct 121 ms 34168 KB Output is correct
45 Correct 123 ms 31376 KB Output is correct
46 Correct 116 ms 33852 KB Output is correct
47 Correct 127 ms 33660 KB Output is correct
48 Correct 120 ms 34436 KB Output is correct
49 Correct 65 ms 10052 KB Output is correct
50 Correct 48 ms 8992 KB Output is correct
51 Correct 98 ms 26040 KB Output is correct
52 Correct 159 ms 37516 KB Output is correct
53 Correct 158 ms 38860 KB Output is correct
54 Correct 159 ms 39396 KB Output is correct
55 Correct 123 ms 35620 KB Output is correct
56 Correct 153 ms 39040 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 93 ms 25208 KB Output is correct
10 Correct 115 ms 30644 KB Output is correct
11 Correct 116 ms 30248 KB Output is correct
12 Correct 132 ms 32100 KB Output is correct
13 Correct 122 ms 33492 KB Output is correct
14 Correct 105 ms 25268 KB Output is correct
15 Correct 238 ms 32544 KB Output is correct
16 Correct 249 ms 31600 KB Output is correct
17 Correct 251 ms 33624 KB Output is correct
18 Correct 361 ms 35084 KB Output is correct
19 Correct 275 ms 34980 KB Output is correct
20 Correct 272 ms 36548 KB Output is correct
21 Correct 290 ms 35624 KB Output is correct
22 Correct 305 ms 36308 KB Output is correct
23 Correct 327 ms 36112 KB Output is correct
24 Correct 281 ms 34732 KB Output is correct
25 Correct 296 ms 35832 KB Output is correct
26 Correct 303 ms 34536 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 572 KB Output is correct
32 Correct 2 ms 596 KB Output is correct
33 Correct 1 ms 700 KB Output is correct
34 Correct 1 ms 596 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 11 ms 4904 KB Output is correct
37 Correct 117 ms 33844 KB Output is correct
38 Correct 126 ms 33768 KB Output is correct
39 Correct 116 ms 33712 KB Output is correct
40 Correct 116 ms 33240 KB Output is correct
41 Correct 127 ms 33196 KB Output is correct
42 Correct 106 ms 30364 KB Output is correct
43 Correct 122 ms 34124 KB Output is correct
44 Correct 113 ms 33748 KB Output is correct
45 Correct 103 ms 35776 KB Output is correct
46 Correct 121 ms 34168 KB Output is correct
47 Correct 21 ms 4856 KB Output is correct
48 Correct 269 ms 37648 KB Output is correct
49 Correct 271 ms 37700 KB Output is correct
50 Correct 245 ms 37628 KB Output is correct
51 Correct 253 ms 37452 KB Output is correct
52 Correct 225 ms 35480 KB Output is correct
53 Correct 195 ms 27716 KB Output is correct
54 Correct 253 ms 38424 KB Output is correct
55 Correct 265 ms 37740 KB Output is correct
56 Correct 316 ms 39292 KB Output is correct
57 Correct 257 ms 38380 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 93 ms 25208 KB Output is correct
11 Correct 115 ms 30644 KB Output is correct
12 Correct 116 ms 30248 KB Output is correct
13 Correct 132 ms 32100 KB Output is correct
14 Correct 122 ms 33492 KB Output is correct
15 Correct 105 ms 25268 KB Output is correct
16 Correct 238 ms 32544 KB Output is correct
17 Correct 249 ms 31600 KB Output is correct
18 Correct 251 ms 33624 KB Output is correct
19 Correct 361 ms 35084 KB Output is correct
20 Correct 275 ms 34980 KB Output is correct
21 Correct 272 ms 36548 KB Output is correct
22 Correct 290 ms 35624 KB Output is correct
23 Correct 305 ms 36308 KB Output is correct
24 Correct 327 ms 36112 KB Output is correct
25 Correct 281 ms 34732 KB Output is correct
26 Correct 296 ms 35832 KB Output is correct
27 Correct 303 ms 34536 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 572 KB Output is correct
33 Correct 2 ms 596 KB Output is correct
34 Correct 1 ms 700 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Correct 11 ms 4904 KB Output is correct
38 Correct 117 ms 33844 KB Output is correct
39 Correct 126 ms 33768 KB Output is correct
40 Correct 116 ms 33712 KB Output is correct
41 Correct 116 ms 33240 KB Output is correct
42 Correct 127 ms 33196 KB Output is correct
43 Correct 106 ms 30364 KB Output is correct
44 Correct 122 ms 34124 KB Output is correct
45 Correct 113 ms 33748 KB Output is correct
46 Correct 103 ms 35776 KB Output is correct
47 Correct 121 ms 34168 KB Output is correct
48 Correct 21 ms 4856 KB Output is correct
49 Correct 269 ms 37648 KB Output is correct
50 Correct 271 ms 37700 KB Output is correct
51 Correct 245 ms 37628 KB Output is correct
52 Correct 253 ms 37452 KB Output is correct
53 Correct 225 ms 35480 KB Output is correct
54 Correct 195 ms 27716 KB Output is correct
55 Correct 253 ms 38424 KB Output is correct
56 Correct 265 ms 37740 KB Output is correct
57 Correct 316 ms 39292 KB Output is correct
58 Correct 257 ms 38380 KB Output is correct
59 Correct 93 ms 8584 KB Output is correct
60 Correct 234 ms 32852 KB Output is correct
61 Correct 259 ms 31916 KB Output is correct
62 Correct 258 ms 33936 KB Output is correct
63 Correct 404 ms 35476 KB Output is correct
64 Correct 1 ms 560 KB Output is correct
65 Correct 1 ms 596 KB Output is correct
66 Correct 1 ms 564 KB Output is correct
67 Correct 1 ms 468 KB Output is correct
68 Correct 1 ms 596 KB Output is correct
69 Correct 2 ms 696 KB Output is correct
70 Correct 2 ms 724 KB Output is correct
71 Correct 2 ms 736 KB Output is correct
72 Correct 1 ms 724 KB Output is correct
73 Correct 2 ms 724 KB Output is correct
74 Correct 123 ms 31376 KB Output is correct
75 Correct 116 ms 33852 KB Output is correct
76 Correct 127 ms 33660 KB Output is correct
77 Correct 120 ms 34436 KB Output is correct
78 Correct 65 ms 10052 KB Output is correct
79 Correct 48 ms 8992 KB Output is correct
80 Correct 98 ms 26040 KB Output is correct
81 Correct 159 ms 37516 KB Output is correct
82 Correct 158 ms 38860 KB Output is correct
83 Correct 159 ms 39396 KB Output is correct
84 Correct 123 ms 35620 KB Output is correct
85 Correct 153 ms 39040 KB Output is correct
86 Correct 70 ms 13072 KB Output is correct
87 Correct 261 ms 37736 KB Output is correct
88 Correct 241 ms 37744 KB Output is correct
89 Correct 275 ms 36308 KB Output is correct
90 Correct 164 ms 13888 KB Output is correct
91 Correct 174 ms 15160 KB Output is correct
92 Correct 279 ms 29764 KB Output is correct
93 Correct 258 ms 41332 KB Output is correct
94 Correct 296 ms 42644 KB Output is correct
95 Correct 296 ms 43376 KB Output is correct
96 Correct 334 ms 39256 KB Output is correct
97 Correct 299 ms 40720 KB Output is correct