oj.uz

Submission #319482

# Submission time Handle Problem Language Result Execution time Memory
319482 2020-11-05T11:09:53 Z knon0501 Swapping Cities (APIO20_swap) C++14
6 / 100
 417 ms 40780 KB 
#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MX=3e5+5;
int sz[MX];
int p[MX][20];
int nn,n;
int pr[MX];
int w[MX];
int dth[MX];
int b[MX];
int E[MX];
int c[MX];
vector<int> a[MX];

struct A{
    int u,v,w;
    bool operator <(const A&r)const{
        return w<r.w;
    }
}e[MX];

int lca(int v,int u){
    int i,j;
    if(dth[v]>dth[u])swap(u,v);
    for(i=19 ; i>=0 ; i--)if(dth[u]-dth[v]>=(1<<i))u=p[u][i];
    if(u==v)return v;
    for(i=19 ; i>=0 ; i--){
        if(p[u][i]!=p[v][i]){
            u=p[u][i];
            v=p[v][i];
        }
    }
    return p[v][0];
}
int f(int k){
    return k==pr[k] ? k:pr[k]=f(pr[k]);
}
void Union(A k){
    int x=f(k.u);
    int y=f(k.v);

    if(x==y){
        E[x]++;
        if(b[x]==-1)
            b[x]=k.w;
        return;
    }
    pr[x]=nn;
    pr[y]=nn;
    sz[nn]=sz[x]+sz[y];
    E[nn]=E[x]+E[y]+1;
    w[nn]=k.w;
    a[nn].push_back(x);
    a[nn].push_back(y);
    p[x][0]=nn;
    p[y][0]=nn;
    if(E[nn]>=sz[nn]){
        b[nn]=k.w;
    }
    nn++;
}
void dfs(int v,int pp){
    if(E[v]>=sz[v])c[v]=v;
    else if(p[v][0]>=0)c[v]=c[p[v][0]];
    else c[v]=-1;
    for(auto u:a[v]){
        if(u==pp)continue;
        dth[u]=dth[v]+1;
        dfs(u,v);
    }
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    nn=n=N;
    int i,j;
    for(i=0 ; i<M; i++){
        e[i]={U[i],V[i],W[i]};
    }
    sort(e,e+M);
    for(i=0 ; i<N+M ; i++)pr[i]=i,sz[i]=1,p[i][0]=-1,b[i]=-1;
    for(i=0 ; i<M ; i++){
        Union(e[i]);

    }
    for(i=0 ; i<nn ; i++)
        if(p[i][0]==-1)
            dfs(i,-1);
    for(i=1 ; i<20 ; i++){
        for(j=0 ; j<nn ; j++){
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }

}

int getMinimumFuelCapacity(int X, int Y) {
    int k=lca(X,Y);
    if(c[k]==-1)return -1;
    return b[c[k]];
}

Compilation message

swap.cpp: In function 'int lca(int, int)':
swap.cpp:25:11: warning: unused variable 'j' [-Wunused-variable]
   25 |     int i,j;
      |           ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 6 ms 7660 KB Output is correct
5 Correct 6 ms 7660 KB Output is correct
6 Correct 6 ms 7788 KB Output is correct
7 Correct 6 ms 7660 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct
9 Correct 119 ms 28644 KB Output is correct
10 Correct 150 ms 33376 KB Output is correct
11 Correct 147 ms 33124 KB Output is correct
12 Correct 155 ms 34660 KB Output is correct
13 Correct 144 ms 37604 KB Output is correct
14 Correct 135 ms 28708 KB Output is correct
15 Correct 295 ms 35312 KB Output is correct
16 Correct 288 ms 34708 KB Output is correct
17 Correct 295 ms 36168 KB Output is correct
18 Correct 417 ms 39500 KB Output is correct
19 Correct 102 ms 15204 KB Output is correct
20 Correct 280 ms 36580 KB Output is correct
21 Correct 283 ms 35868 KB Output is correct
22 Correct 300 ms 37580 KB Output is correct
23 Correct 412 ms 40780 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Incorrect 355 ms 40580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 6 ms 7660 KB Output is correct
6 Correct 6 ms 7660 KB Output is correct
7 Correct 6 ms 7788 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct
9 Correct 6 ms 7660 KB Output is correct
10 Incorrect 6 ms 7660 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 6 ms 7660 KB Output is correct
6 Correct 6 ms 7660 KB Output is correct
7 Correct 6 ms 7788 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct
9 Correct 6 ms 7660 KB Output is correct
10 Correct 119 ms 28644 KB Output is correct
11 Correct 150 ms 33376 KB Output is correct
12 Correct 147 ms 33124 KB Output is correct
13 Correct 155 ms 34660 KB Output is correct
14 Correct 144 ms 37604 KB Output is correct
15 Incorrect 6 ms 7660 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 6 ms 7660 KB Output is correct
5 Correct 6 ms 7660 KB Output is correct
6 Correct 6 ms 7788 KB Output is correct
7 Correct 6 ms 7660 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct
9 Correct 119 ms 28644 KB Output is correct
10 Correct 150 ms 33376 KB Output is correct
11 Correct 147 ms 33124 KB Output is correct
12 Correct 155 ms 34660 KB Output is correct
13 Correct 144 ms 37604 KB Output is correct
14 Correct 135 ms 28708 KB Output is correct
15 Correct 295 ms 35312 KB Output is correct
16 Correct 288 ms 34708 KB Output is correct
17 Correct 295 ms 36168 KB Output is correct
18 Correct 417 ms 39500 KB Output is correct
19 Incorrect 355 ms 40580 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 6 ms 7660 KB Output is correct
6 Correct 6 ms 7660 KB Output is correct
7 Correct 6 ms 7788 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct
9 Correct 6 ms 7660 KB Output is correct
10 Correct 119 ms 28644 KB Output is correct
11 Correct 150 ms 33376 KB Output is correct
12 Correct 147 ms 33124 KB Output is correct
13 Correct 155 ms 34660 KB Output is correct
14 Correct 144 ms 37604 KB Output is correct
15 Correct 135 ms 28708 KB Output is correct
16 Correct 295 ms 35312 KB Output is correct
17 Correct 288 ms 34708 KB Output is correct
18 Correct 295 ms 36168 KB Output is correct
19 Correct 417 ms 39500 KB Output is correct
20 Incorrect 355 ms 40580 KB Output isn't correct
21 Halted 0 ms 0 KB -