oj.uz

Submission #965810

# Submission time Handle Problem Language Result Execution time Memory
965810 2024-04-19T07:29:28 Z owoovo Swapping Cities (APIO20_swap) C++17
13 / 100
 177 ms 32232 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,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,u);
        wh[now]=min(wh[x],wh[now]);
    }
    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 6576 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 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 51 ms 25284 KB Output is correct
10 Correct 67 ms 26712 KB Output is correct
11 Correct 65 ms 26564 KB Output is correct
12 Correct 89 ms 27084 KB Output is correct
13 Correct 67 ms 27324 KB Output is correct
14 Correct 66 ms 25556 KB Output is correct
15 Correct 159 ms 30844 KB Output is correct
16 Correct 148 ms 30920 KB Output is correct
17 Correct 176 ms 31608 KB Output is correct
18 Correct 146 ms 31836 KB Output is correct
19 Correct 74 ms 14336 KB Output is correct
20 Correct 149 ms 31176 KB Output is correct
21 Correct 159 ms 31156 KB Output is correct
22 Correct 174 ms 32232 KB Output is correct
23 Correct 175 ms 32036 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 6576 KB Output is correct
3 Correct 158 ms 28684 KB Output is correct
4 Correct 159 ms 31396 KB Output is correct
5 Correct 155 ms 31212 KB Output is correct
6 Correct 177 ms 31256 KB Output is correct
7 Correct 144 ms 31172 KB Output is correct
8 Correct 157 ms 31052 KB Output is correct
9 Correct 167 ms 31028 KB Output is correct
10 Correct 145 ms 30900 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 6576 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 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 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 Incorrect 2 ms 6492 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6576 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 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 51 ms 25284 KB Output is correct
11 Correct 67 ms 26712 KB Output is correct
12 Correct 65 ms 26564 KB Output is correct
13 Correct 89 ms 27084 KB Output is correct
14 Correct 67 ms 27324 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 Incorrect 2 ms 6492 KB Output isn't correct
21 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 6576 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 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 51 ms 25284 KB Output is correct
10 Correct 67 ms 26712 KB Output is correct
11 Correct 65 ms 26564 KB Output is correct
12 Correct 89 ms 27084 KB Output is correct
13 Correct 67 ms 27324 KB Output is correct
14 Correct 66 ms 25556 KB Output is correct
15 Correct 159 ms 30844 KB Output is correct
16 Correct 148 ms 30920 KB Output is correct
17 Correct 176 ms 31608 KB Output is correct
18 Correct 146 ms 31836 KB Output is correct
19 Correct 158 ms 28684 KB Output is correct
20 Correct 159 ms 31396 KB Output is correct
21 Correct 155 ms 31212 KB Output is correct
22 Correct 177 ms 31256 KB Output is correct
23 Correct 144 ms 31172 KB Output is correct
24 Correct 157 ms 31052 KB Output is correct
25 Correct 167 ms 31028 KB Output is correct
26 Correct 145 ms 30900 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 Incorrect 2 ms 6492 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6576 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 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 51 ms 25284 KB Output is correct
11 Correct 67 ms 26712 KB Output is correct
12 Correct 65 ms 26564 KB Output is correct
13 Correct 89 ms 27084 KB Output is correct
14 Correct 67 ms 27324 KB Output is correct
15 Correct 66 ms 25556 KB Output is correct
16 Correct 159 ms 30844 KB Output is correct
17 Correct 148 ms 30920 KB Output is correct
18 Correct 176 ms 31608 KB Output is correct
19 Correct 146 ms 31836 KB Output is correct
20 Correct 158 ms 28684 KB Output is correct
21 Correct 159 ms 31396 KB Output is correct
22 Correct 155 ms 31212 KB Output is correct
23 Correct 177 ms 31256 KB Output is correct
24 Correct 144 ms 31172 KB Output is correct
25 Correct 157 ms 31052 KB Output is correct
26 Correct 167 ms 31028 KB Output is correct
27 Correct 145 ms 30900 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 Incorrect 2 ms 6492 KB Output isn't correct
34 Halted 0 ms 0 KB -