oj.uz

Submission #319483

# Submission time Handle Problem Language Result Execution time Memory
319483 2020-11-05T11:25:25 Z knon0501 Swapping Cities (APIO20_swap) C++14
6 / 100
 413 ms 41676 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];
int deg[MX];
int mdeg[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){
    deg[k.u]++;
    deg[k.v]++;

    int x=f(k.u);
    int y=f(k.v);

    if(x==y){
        E[x]++;
        mdeg[x]=max({mdeg[x],deg[k.u],deg[k.v]});
        if(b[x]==-1)
            b[x]=k.w;
        return;
    }
    pr[x]=nn;
    pr[y]=nn;
    mdeg[nn]=max({mdeg[x],mdeg[y],deg[k.u],deg[k.v]});
    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]==-1 ){
        b[nn]=k.w;
    }
    if(mdeg[nn]>=3 && b[nn]==-1)
        b[nn]=k.w;
    nn++;
}
void dfs(int v,int pp){
    if(E[v]>=sz[v] || mdeg[nn]>=3)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 ; i++)sz[i]=1;
    for(i=0 ; i<N+M ; i++)pr[i]=i,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:27:11: warning: unused variable 'j' [-Wunused-variable]
   27 |     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 7552 KB Output is correct
5 Correct 6 ms 7788 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 7808 KB Output is correct
9 Correct 123 ms 29284 KB Output is correct
10 Correct 153 ms 34276 KB Output is correct
11 Correct 149 ms 33892 KB Output is correct
12 Correct 157 ms 35300 KB Output is correct
13 Correct 145 ms 38372 KB Output is correct
14 Correct 137 ms 29284 KB Output is correct
15 Correct 296 ms 36236 KB Output is correct
16 Correct 305 ms 35492 KB Output is correct
17 Correct 302 ms 37208 KB Output is correct
18 Correct 410 ms 40140 KB Output is correct
19 Correct 105 ms 15332 KB Output is correct
20 Correct 291 ms 37496 KB Output is correct
21 Correct 296 ms 36512 KB Output is correct
22 Correct 310 ms 38476 KB Output is correct
23 Correct 413 ms 41676 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 362 ms 41352 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 7552 KB Output is correct
6 Correct 6 ms 7788 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 7808 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 7552 KB Output is correct
6 Correct 6 ms 7788 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 7808 KB Output is correct
10 Correct 123 ms 29284 KB Output is correct
11 Correct 153 ms 34276 KB Output is correct
12 Correct 149 ms 33892 KB Output is correct
13 Correct 157 ms 35300 KB Output is correct
14 Correct 145 ms 38372 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 7552 KB Output is correct
5 Correct 6 ms 7788 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 7808 KB Output is correct
9 Correct 123 ms 29284 KB Output is correct
10 Correct 153 ms 34276 KB Output is correct
11 Correct 149 ms 33892 KB Output is correct
12 Correct 157 ms 35300 KB Output is correct
13 Correct 145 ms 38372 KB Output is correct
14 Correct 137 ms 29284 KB Output is correct
15 Correct 296 ms 36236 KB Output is correct
16 Correct 305 ms 35492 KB Output is correct
17 Correct 302 ms 37208 KB Output is correct
18 Correct 410 ms 40140 KB Output is correct
19 Incorrect 362 ms 41352 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 7552 KB Output is correct
6 Correct 6 ms 7788 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 7808 KB Output is correct
10 Correct 123 ms 29284 KB Output is correct
11 Correct 153 ms 34276 KB Output is correct
12 Correct 149 ms 33892 KB Output is correct
13 Correct 157 ms 35300 KB Output is correct
14 Correct 145 ms 38372 KB Output is correct
15 Correct 137 ms 29284 KB Output is correct
16 Correct 296 ms 36236 KB Output is correct
17 Correct 305 ms 35492 KB Output is correct
18 Correct 302 ms 37208 KB Output is correct
19 Correct 410 ms 40140 KB Output is correct
20 Incorrect 362 ms 41352 KB Output isn't correct
21 Halted 0 ms 0 KB -