oj.uz

Submission #1095950

# Submission time Handle Problem Language Result Execution time Memory
1095950 2024-10-03T12:51:49 Z onlk97 Swapping Cities (APIO20_swap) C++14
6 / 100
 167 ms 39444 KB 
#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){
    return a.second<b.second;
}
struct dsu{
    vector <int> pa;
    void init(int n){
        pa.clear();
        for (int i=0; i<=n; i++) pa.push_back(i);
    }
    int prt(int n){
        if (pa[n]==n) return n;
        return pa[n]=prt(pa[n]);
    }
    void unn(int u,int v){
        pa[prt(u)]=pa[prt(v)];
    }
};
int weight[200010],lb[200010],dep[200010];
vector <int> krt[200010];
void dfs1(int cur,int prv){
    if (prv!=-1) dep[cur]=dep[prv]+1;
    for (int i:krt[cur]) dfs1(i,cur);
    if (lb[cur]) weight[cur]=max(lb[cur],min(weight[krt[cur][0]],weight[krt[cur][1]]));
}
void dfs2(int cur,int mn){
    weight[cur]=min(weight[cur],mn);
    for (int i:krt[cur]) dfs2(i,min(mn,weight[cur]));
}
int fa[20][2000010];
int lca(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);
    int d=dep[u]-dep[v];
    for (int i=0; i<20; i++){
        if (d&(1<<i)) u=fa[i][u];
    }
    if (u==v) return u;
    for (int i=19; i>=0; i--){
        if (fa[i][u]!=fa[i][v]){
            u=fa[i][u];
            v=fa[i][v];
        }
    }
    return fa[0][u];
}
void init(int N,int M,vector <int> U,vector <int> V,vector <int> W){
    pair <pair <int,int>,int> edg[M];
    for (int i=0; i<M; i++) edg[i]={{U[i]+1,V[i]+1},W[i]};
    sort(edg,edg+M,cmp);
    dsu d;
    d.init(2*N);
    int cnt=N;
    for (int i=0; i<=2*N; i++) weight[i]=2e9;
    for (int i=0; i<M; i++){
        int u=d.prt(edg[i].first.first),v=d.prt(edg[i].first.second);
        if (u==v){
            weight[edg[i].first.first]=min(weight[edg[i].first.first],edg[i].second);
            weight[edg[i].first.second]=min(weight[edg[i].first.second],edg[i].second);
            continue;
        }
        cnt++;
        d.unn(u,cnt);
        d.unn(v,cnt);
        krt[cnt].push_back(u); krt[cnt].push_back(v);
        fa[0][u]=cnt; fa[0][v]=cnt;
        lb[cnt]=edg[i].second;
    }
    dfs1(cnt,-1);
    dfs2(cnt,2e9);
    for (int i=1; i<20; i++){
        for (int j=1; j<=cnt; j++) fa[i][j]=fa[i-1][fa[i-1][j]];
    }
}

int getMinimumFuelCapacity(int X,int Y){
    X++; Y++;
    int l=lca(X,Y);
    int ans=weight[l];
    if (ans>1e9) ans=-1;
    return ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 3 ms 5428 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 51 ms 26596 KB Output is correct
10 Correct 63 ms 31176 KB Output is correct
11 Correct 58 ms 30864 KB Output is correct
12 Correct 63 ms 32452 KB Output is correct
13 Correct 54 ms 34760 KB Output is correct
14 Correct 53 ms 26820 KB Output is correct
15 Correct 120 ms 35196 KB Output is correct
16 Correct 120 ms 34544 KB Output is correct
17 Correct 123 ms 36292 KB Output is correct
18 Correct 167 ms 38600 KB Output is correct
19 Correct 56 ms 14548 KB Output is correct
20 Correct 127 ms 35904 KB Output is correct
21 Correct 134 ms 35240 KB Output is correct
22 Correct 138 ms 37140 KB Output is correct
23 Correct 165 ms 39444 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Incorrect 147 ms 38600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 3 ms 5428 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Incorrect 3 ms 5468 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5464 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 3 ms 5428 KB Output is correct
9 Correct 3 ms 5468 KB Output is correct
10 Correct 51 ms 26596 KB Output is correct
11 Correct 63 ms 31176 KB Output is correct
12 Correct 58 ms 30864 KB Output is correct
13 Correct 63 ms 32452 KB Output is correct
14 Correct 54 ms 34760 KB Output is correct
15 Incorrect 3 ms 5468 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 3 ms 5428 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 51 ms 26596 KB Output is correct
10 Correct 63 ms 31176 KB Output is correct
11 Correct 58 ms 30864 KB Output is correct
12 Correct 63 ms 32452 KB Output is correct
13 Correct 54 ms 34760 KB Output is correct
14 Correct 53 ms 26820 KB Output is correct
15 Correct 120 ms 35196 KB Output is correct
16 Correct 120 ms 34544 KB Output is correct
17 Correct 123 ms 36292 KB Output is correct
18 Correct 167 ms 38600 KB Output is correct
19 Incorrect 147 ms 38600 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5464 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 3 ms 5428 KB Output is correct
9 Correct 3 ms 5468 KB Output is correct
10 Correct 51 ms 26596 KB Output is correct
11 Correct 63 ms 31176 KB Output is correct
12 Correct 58 ms 30864 KB Output is correct
13 Correct 63 ms 32452 KB Output is correct
14 Correct 54 ms 34760 KB Output is correct
15 Correct 53 ms 26820 KB Output is correct
16 Correct 120 ms 35196 KB Output is correct
17 Correct 120 ms 34544 KB Output is correct
18 Correct 123 ms 36292 KB Output is correct
19 Correct 167 ms 38600 KB Output is correct
20 Incorrect 147 ms 38600 KB Output isn't correct
21 Halted 0 ms 0 KB -