oj.uz

Submission #965864

# Submission time Handle Problem Language Result Execution time Memory
965864 2024-04-19T07:38:48 Z owoovo Swapping Cities (APIO20_swap) C++17
13 / 100
 186 ms 31992 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);
        wh[b]=min(wh[b],wh[a]);
        e[a].push_back(b),e[b].push_back(a);
        return;
    }
}dsu;
void dfs(int now,int last,int w){
    int u=w;
    u=min(u,wh[now]);
    wh[now]=min(u,wh[now]);
    dep[now]=dep[last]+1;
    for(auto x:e[now]){
        if(x==last)continue;
        dfs(x,now,max(u,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,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 2 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 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 55 ms 26452 KB Output is correct
10 Correct 72 ms 28220 KB Output is correct
11 Correct 81 ms 28340 KB Output is correct
12 Correct 81 ms 28724 KB Output is correct
13 Correct 70 ms 28884 KB Output is correct
14 Correct 66 ms 26824 KB Output is correct
15 Correct 157 ms 31132 KB Output is correct
16 Correct 150 ms 30972 KB Output is correct
17 Correct 168 ms 31604 KB Output is correct
18 Correct 186 ms 31604 KB Output is correct
19 Correct 59 ms 14676 KB Output is correct
20 Correct 156 ms 31172 KB Output is correct
21 Correct 169 ms 31324 KB Output is correct
22 Correct 175 ms 31892 KB Output is correct
23 Correct 157 ms 31992 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 141 ms 31236 KB Output is correct
4 Correct 142 ms 31632 KB Output is correct
5 Correct 148 ms 31560 KB Output is correct
6 Correct 143 ms 31328 KB Output is correct
7 Correct 139 ms 31664 KB Output is correct
8 Correct 137 ms 31320 KB Output is correct
9 Correct 145 ms 31432 KB Output is correct
10 Correct 145 ms 31096 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 1 ms 6492 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 6576 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 6620 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 1 ms 6492 KB Output is correct
24 Incorrect 2 ms 6752 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 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 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 55 ms 26452 KB Output is correct
11 Correct 72 ms 28220 KB Output is correct
12 Correct 81 ms 28340 KB Output is correct
13 Correct 81 ms 28724 KB Output is correct
14 Correct 70 ms 28884 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 6576 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 6620 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 6492 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 2 ms 6492 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Incorrect 2 ms 6752 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 55 ms 26452 KB Output is correct
10 Correct 72 ms 28220 KB Output is correct
11 Correct 81 ms 28340 KB Output is correct
12 Correct 81 ms 28724 KB Output is correct
13 Correct 70 ms 28884 KB Output is correct
14 Correct 66 ms 26824 KB Output is correct
15 Correct 157 ms 31132 KB Output is correct
16 Correct 150 ms 30972 KB Output is correct
17 Correct 168 ms 31604 KB Output is correct
18 Correct 186 ms 31604 KB Output is correct
19 Correct 141 ms 31236 KB Output is correct
20 Correct 142 ms 31632 KB Output is correct
21 Correct 148 ms 31560 KB Output is correct
22 Correct 143 ms 31328 KB Output is correct
23 Correct 139 ms 31664 KB Output is correct
24 Correct 137 ms 31320 KB Output is correct
25 Correct 145 ms 31432 KB Output is correct
26 Correct 145 ms 31096 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 6576 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 6620 KB Output is correct
34 Correct 2 ms 6492 KB Output is correct
35 Correct 2 ms 6492 KB Output is correct
36 Correct 8 ms 7964 KB Output is correct
37 Correct 82 ms 28496 KB Output is correct
38 Correct 73 ms 28356 KB Output is correct
39 Correct 81 ms 28464 KB Output is correct
40 Correct 74 ms 28368 KB Output is correct
41 Correct 84 ms 28300 KB Output is correct
42 Correct 63 ms 27592 KB Output is correct
43 Incorrect 72 ms 28868 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 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 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 55 ms 26452 KB Output is correct
11 Correct 72 ms 28220 KB Output is correct
12 Correct 81 ms 28340 KB Output is correct
13 Correct 81 ms 28724 KB Output is correct
14 Correct 70 ms 28884 KB Output is correct
15 Correct 66 ms 26824 KB Output is correct
16 Correct 157 ms 31132 KB Output is correct
17 Correct 150 ms 30972 KB Output is correct
18 Correct 168 ms 31604 KB Output is correct
19 Correct 186 ms 31604 KB Output is correct
20 Correct 141 ms 31236 KB Output is correct
21 Correct 142 ms 31632 KB Output is correct
22 Correct 148 ms 31560 KB Output is correct
23 Correct 143 ms 31328 KB Output is correct
24 Correct 139 ms 31664 KB Output is correct
25 Correct 137 ms 31320 KB Output is correct
26 Correct 145 ms 31432 KB Output is correct
27 Correct 145 ms 31096 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 6576 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 6620 KB Output is correct
35 Correct 2 ms 6492 KB Output is correct
36 Correct 2 ms 6492 KB Output is correct
37 Correct 8 ms 7964 KB Output is correct
38 Correct 82 ms 28496 KB Output is correct
39 Correct 73 ms 28356 KB Output is correct
40 Correct 81 ms 28464 KB Output is correct
41 Correct 74 ms 28368 KB Output is correct
42 Correct 84 ms 28300 KB Output is correct
43 Correct 63 ms 27592 KB Output is correct
44 Incorrect 72 ms 28868 KB Output isn't correct
45 Halted 0 ms 0 KB -