oj.uz

Submission #965883

# Submission time Handle Problem Language Result Execution time Memory
965883 2024-04-19T07:45:05 Z owoovo Swapping Cities (APIO20_swap) C++17
100 / 100
 189 ms 39256 KB 
#include "swap.h"
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
const int maxn=1e9+10;
int deg[100010],tag[100010],wh[100010],dep[100010],jpt[100010][20],jpw[100010][20];
vector<int> e[100010];
struct Dsu{
    int ori[100010]={},si[100010]={};
    void init(int n){
        for(int i=0;i<n;i++)ori[i]=i,si[i]=1;
        return ;
    }
    int f(int a){
        return a==ori[a]?a:f(ori[a]);
    }
    void onion(int a,int b,int w){
        int ok=0;
        if(deg[a]>=3||deg[b]>=3)ok=1;
        a=f(a),b=f(b);
        if(a==b){
            wh[a]=min(wh[a],w);
            return ;
        }
        if(si[a]>si[b])swap(a,b);
        si[b]+=si[a];
        ori[a]=b;
        jpt[a][0]=b;
        jpw[a][0]=w;
        if(ok)wh[b]=min(wh[b],w);
        e[a].push_back(b),e[b].push_back(a);
        return;
    }
}dsu;
void dfs(int now,int last){
    dep[now]=dep[last]+1;
    for(auto x:e[now]){
        if(x==last)continue;
        dfs(x,now);
        wh[now]=min(wh[now],max(wh[x],jpw[x][0]));
    }
    return;
}
void dfs2(int now,int last,int w){
    w=min(w,wh[now]);
    wh[now]=min(wh[now],w);
    for(auto x:e[now]){
        if(x==last)continue;
        dfs2(x,now,max(w,jpw[x][0]));
    }
    return ;
}
void init(int n, int m,vector<int> u, vector<int> v, vector<int> w) {
    for(int i=0;i<n;i++)wh[i]=maxn;
    dsu.init(n);
    vector<pair<int,pair<int,int>>>edge;
    for(int i=0;i<m;i++)edge.push_back({w[i],{u[i],v[i]}});
    sort(edge.begin(),edge.end());
    for(auto [x,y]:edge){
        auto [q,r]=y;
        deg[q]++;
        deg[r]++;
        dsu.onion(q,r,x);
    }
    for(int i=1;i<=18;i++){
        for(int j=0;j<n;j++){
            jpt[j][i]=jpt[jpt[j][i-1]][i-1];
            jpw[j][i]=max(jpw[j][i-1],jpw[jpt[j][i-1]][i-1]);
        }
    }
    for(int i=0;i<n;i++)if(i==dsu.ori[i])dfs(i,i),dfs2(i,i,maxn);
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int ans=0;
    for(int i=18;i>=0;i--){
        if(dep[u]-(1<<i)>=dep[v]){
            //cout<<jpw[u][i]<<" "<<u<<" k\n";
            ans=max(ans,jpw[u][i]);
            u=jpt[u][i];
        }
    }
    if(u==v){
        //cout<<ans<<" "<<wh[u]<<"\n";

        return max(ans,wh[u]);
    }
    for(int i=18;i>=0;i--){
        if(jpt[u][i]!=jpt[v][i]){
            ans=max(ans,jpw[u][i]);
            ans=max(ans,jpw[v][i]);
            u=jpt[u][i];
            v=jpt[v][i];
        }
    }
    ans=max(ans,jpw[u][0]);
    ans=max(ans,jpw[v][0]);
    u=jpt[u][0];
    //cout<<ans<<" "<<wh[u]<<"\n";
    return max(ans,wh[u]);
}
int getMinimumFuelCapacity(int u, int v) {
    int ans=lca(u,v);
    return ans==maxn?-1:ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6580 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6684 KB Output is correct
9 Correct 55 ms 25264 KB Output is correct
10 Correct 72 ms 26824 KB Output is correct
11 Correct 70 ms 26572 KB Output is correct
12 Correct 82 ms 27208 KB Output is correct
13 Correct 82 ms 27244 KB Output is correct
14 Correct 65 ms 25540 KB Output is correct
15 Correct 148 ms 28360 KB Output is correct
16 Correct 186 ms 28048 KB Output is correct
17 Correct 157 ms 29136 KB Output is correct
18 Correct 157 ms 28896 KB Output is correct
19 Correct 56 ms 13140 KB Output is correct
20 Correct 153 ms 28612 KB Output is correct
21 Correct 143 ms 28596 KB Output is correct
22 Correct 153 ms 29340 KB Output is correct
23 Correct 148 ms 29264 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 139 ms 28728 KB Output is correct
4 Correct 151 ms 29044 KB Output is correct
5 Correct 134 ms 28860 KB Output is correct
6 Correct 133 ms 28836 KB Output is correct
7 Correct 135 ms 28868 KB Output is correct
8 Correct 126 ms 28708 KB Output is correct
9 Correct 138 ms 28872 KB Output is correct
10 Correct 126 ms 28728 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6580 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6684 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 2 ms 6748 KB Output is correct
26 Correct 2 ms 6744 KB Output is correct
27 Correct 3 ms 6748 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6580 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6684 KB Output is correct
10 Correct 55 ms 25264 KB Output is correct
11 Correct 72 ms 26824 KB Output is correct
12 Correct 70 ms 26572 KB Output is correct
13 Correct 82 ms 27208 KB Output is correct
14 Correct 82 ms 27244 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 2 ms 6492 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct
31 Correct 2 ms 6744 KB Output is correct
32 Correct 3 ms 6748 KB Output is correct
33 Correct 2 ms 6748 KB Output is correct
34 Correct 7 ms 7708 KB Output is correct
35 Correct 75 ms 27332 KB Output is correct
36 Correct 78 ms 27196 KB Output is correct
37 Correct 92 ms 27184 KB Output is correct
38 Correct 70 ms 27080 KB Output is correct
39 Correct 70 ms 27000 KB Output is correct
40 Correct 76 ms 26216 KB Output is correct
41 Correct 76 ms 27332 KB Output is correct
42 Correct 74 ms 28776 KB Output is correct
43 Correct 65 ms 29208 KB Output is correct
44 Correct 72 ms 29120 KB Output is correct
45 Correct 80 ms 31172 KB Output is correct
46 Correct 75 ms 28668 KB Output is correct
47 Correct 82 ms 28612 KB Output is correct
48 Correct 82 ms 29084 KB Output is correct
49 Correct 50 ms 15072 KB Output is correct
50 Correct 40 ms 13272 KB Output is correct
51 Correct 71 ms 24748 KB Output is correct
52 Correct 98 ms 32708 KB Output is correct
53 Correct 102 ms 33240 KB Output is correct
54 Correct 108 ms 34752 KB Output is correct
55 Correct 71 ms 28900 KB Output is correct
56 Correct 97 ms 32960 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6580 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6684 KB Output is correct
9 Correct 55 ms 25264 KB Output is correct
10 Correct 72 ms 26824 KB Output is correct
11 Correct 70 ms 26572 KB Output is correct
12 Correct 82 ms 27208 KB Output is correct
13 Correct 82 ms 27244 KB Output is correct
14 Correct 65 ms 25540 KB Output is correct
15 Correct 148 ms 28360 KB Output is correct
16 Correct 186 ms 28048 KB Output is correct
17 Correct 157 ms 29136 KB Output is correct
18 Correct 157 ms 28896 KB Output is correct
19 Correct 139 ms 28728 KB Output is correct
20 Correct 151 ms 29044 KB Output is correct
21 Correct 134 ms 28860 KB Output is correct
22 Correct 133 ms 28836 KB Output is correct
23 Correct 135 ms 28868 KB Output is correct
24 Correct 126 ms 28708 KB Output is correct
25 Correct 138 ms 28872 KB Output is correct
26 Correct 126 ms 28728 KB Output is correct
27 Correct 2 ms 6492 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 2 ms 6492 KB Output is correct
31 Correct 2 ms 6492 KB Output is correct
32 Correct 2 ms 6492 KB Output is correct
33 Correct 2 ms 6492 KB Output is correct
34 Correct 2 ms 6492 KB Output is correct
35 Correct 2 ms 6492 KB Output is correct
36 Correct 7 ms 7708 KB Output is correct
37 Correct 75 ms 27332 KB Output is correct
38 Correct 78 ms 27196 KB Output is correct
39 Correct 92 ms 27184 KB Output is correct
40 Correct 70 ms 27080 KB Output is correct
41 Correct 70 ms 27000 KB Output is correct
42 Correct 76 ms 26216 KB Output is correct
43 Correct 76 ms 27332 KB Output is correct
44 Correct 74 ms 28776 KB Output is correct
45 Correct 65 ms 29208 KB Output is correct
46 Correct 72 ms 29120 KB Output is correct
47 Correct 13 ms 8324 KB Output is correct
48 Correct 176 ms 32848 KB Output is correct
49 Correct 168 ms 32968 KB Output is correct
50 Correct 185 ms 32960 KB Output is correct
51 Correct 183 ms 32712 KB Output is correct
52 Correct 143 ms 32144 KB Output is correct
53 Correct 118 ms 26792 KB Output is correct
54 Correct 150 ms 33680 KB Output is correct
55 Correct 177 ms 33024 KB Output is correct
56 Correct 163 ms 32964 KB Output is correct
57 Correct 149 ms 33772 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6580 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6684 KB Output is correct
10 Correct 55 ms 25264 KB Output is correct
11 Correct 72 ms 26824 KB Output is correct
12 Correct 70 ms 26572 KB Output is correct
13 Correct 82 ms 27208 KB Output is correct
14 Correct 82 ms 27244 KB Output is correct
15 Correct 65 ms 25540 KB Output is correct
16 Correct 148 ms 28360 KB Output is correct
17 Correct 186 ms 28048 KB Output is correct
18 Correct 157 ms 29136 KB Output is correct
19 Correct 157 ms 28896 KB Output is correct
20 Correct 139 ms 28728 KB Output is correct
21 Correct 151 ms 29044 KB Output is correct
22 Correct 134 ms 28860 KB Output is correct
23 Correct 133 ms 28836 KB Output is correct
24 Correct 135 ms 28868 KB Output is correct
25 Correct 126 ms 28708 KB Output is correct
26 Correct 138 ms 28872 KB Output is correct
27 Correct 126 ms 28728 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 2 ms 6492 KB Output is correct
31 Correct 2 ms 6492 KB Output is correct
32 Correct 2 ms 6492 KB Output is correct
33 Correct 2 ms 6492 KB Output is correct
34 Correct 2 ms 6492 KB Output is correct
35 Correct 2 ms 6492 KB Output is correct
36 Correct 2 ms 6492 KB Output is correct
37 Correct 7 ms 7708 KB Output is correct
38 Correct 75 ms 27332 KB Output is correct
39 Correct 78 ms 27196 KB Output is correct
40 Correct 92 ms 27184 KB Output is correct
41 Correct 70 ms 27080 KB Output is correct
42 Correct 70 ms 27000 KB Output is correct
43 Correct 76 ms 26216 KB Output is correct
44 Correct 76 ms 27332 KB Output is correct
45 Correct 74 ms 28776 KB Output is correct
46 Correct 65 ms 29208 KB Output is correct
47 Correct 72 ms 29120 KB Output is correct
48 Correct 13 ms 8324 KB Output is correct
49 Correct 176 ms 32848 KB Output is correct
50 Correct 168 ms 32968 KB Output is correct
51 Correct 185 ms 32960 KB Output is correct
52 Correct 183 ms 32712 KB Output is correct
53 Correct 143 ms 32144 KB Output is correct
54 Correct 118 ms 26792 KB Output is correct
55 Correct 150 ms 33680 KB Output is correct
56 Correct 177 ms 33024 KB Output is correct
57 Correct 163 ms 32964 KB Output is correct
58 Correct 149 ms 33772 KB Output is correct
59 Correct 56 ms 13140 KB Output is correct
60 Correct 153 ms 28612 KB Output is correct
61 Correct 143 ms 28596 KB Output is correct
62 Correct 153 ms 29340 KB Output is correct
63 Correct 148 ms 29264 KB Output is correct
64 Correct 2 ms 6492 KB Output is correct
65 Correct 1 ms 6492 KB Output is correct
66 Correct 1 ms 6492 KB Output is correct
67 Correct 2 ms 6492 KB Output is correct
68 Correct 2 ms 6492 KB Output is correct
69 Correct 2 ms 6492 KB Output is correct
70 Correct 2 ms 6748 KB Output is correct
71 Correct 2 ms 6744 KB Output is correct
72 Correct 3 ms 6748 KB Output is correct
73 Correct 2 ms 6748 KB Output is correct
74 Correct 80 ms 31172 KB Output is correct
75 Correct 75 ms 28668 KB Output is correct
76 Correct 82 ms 28612 KB Output is correct
77 Correct 82 ms 29084 KB Output is correct
78 Correct 50 ms 15072 KB Output is correct
79 Correct 40 ms 13272 KB Output is correct
80 Correct 71 ms 24748 KB Output is correct
81 Correct 98 ms 32708 KB Output is correct
82 Correct 102 ms 33240 KB Output is correct
83 Correct 108 ms 34752 KB Output is correct
84 Correct 71 ms 28900 KB Output is correct
85 Correct 97 ms 32960 KB Output is correct
86 Correct 41 ms 15820 KB Output is correct
87 Correct 152 ms 32968 KB Output is correct
88 Correct 164 ms 32836 KB Output is correct
89 Correct 148 ms 32792 KB Output is correct
90 Correct 106 ms 19900 KB Output is correct
91 Correct 105 ms 19904 KB Output is correct
92 Correct 134 ms 28616 KB Output is correct
93 Correct 174 ms 37504 KB Output is correct
94 Correct 183 ms 38228 KB Output is correct
95 Correct 189 ms 39256 KB Output is correct
96 Correct 146 ms 32964 KB Output is correct
97 Correct 169 ms 35264 KB Output is correct