oj.uz

Submission #403567

# Submission time Handle Problem Language Result Execution time Memory
403567 2021-05-13T09:37:45 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
0 / 100
 493 ms 69524 KB 
#include "swap.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct A{
    int u,v,w;
    bool operator < (const A&o) const{
        return w<o.w;
    }
};
A e[200010];
vector<A> g[100010],g2[100010];
int p[100010],pa[20][100010],mx[20][100010],mark[200010],miout[100010],mi[20][100010],mi2[20][100010],mi3[20][100010],h[100010],cnt;
int fr(int i){
    if(p[i]==i) return p[i];
    return p[i]=fr(p[i]);
}
void dfs(int i,int prev,int weight){
    pa[0][i]=prev;
    mx[0][i]=weight;
    for(auto x : g[i]){
        if(mark[x.v]==0) {
            miout[i]=min(miout[i],x.w);
            miout[x.u]=min(miout[x.u],x.w);
            continue;
        }
        if(x.u==prev) continue;
        h[x.u]=h[i]+1;
        dfs(x.u,i,x.w);
        g2[i].push_back({x.u,x.v,x.w});
    }
}
void init(int N, int M,vector<int> u,vector<int> v,vector<int> w) {
    int i,j,pu,pv;
    n=N;
    m=M;
    for(i=0;i<N;i++){
        p[i]=i;
    }
    for(i=0;i<M;i++){
        e[i]={u[i],v[i],w[i]};
    }
    sort(e,e+M);
    for(i=0;i<M;i++){
        g[e[i].u].push_back({e[i].v,i,e[i].w});
        g[e[i].v].push_back({e[i].u,i,e[i].w});
    }
    for(i=0;i<M;i++){
        pu=fr(e[i].u);
        pv=fr(e[i].v);
        if(pu==pv) continue;
        mark[i]=1;
        p[pu]=pv;
    }
    memset(miout,127,sizeof miout);
    memset(mi,127,sizeof mi);
    memset(mi2,127,sizeof mi2);
    memset(mi3,127,sizeof mi3);
    memset(h,-1,sizeof h);
    memset(pa,-1,sizeof pa);
    h[0]=0;
    dfs(0,-1,-1);
    for(j=0;j<N;j++) sort(g2[i].begin(),g2[i].end()),mi[0][j]=mi2[0][j]=mi3[0][j]=miout[j];
    for(j=0;j<N;j++){
        if(g2[j].size()>=1){
            mi[0][j]=min(mi[0][j],g2[j][0].w);
        }
        if(g2[j].size()>=2){
            mi2[0][j]=min(mi2[0][j],g2[j][1].w);
        }
        if(g2[j].size()>=3){
            mi3[0][j]=min(mi3[0][j],g2[j][2].w);
        }
    }
    for(i=1;i<20;i++){
        for(j=1;j<N;j++){
            pa[i][j]=pa[i-1][pa[i-1][j]];
            mx[i][j]=max(mx[i-1][j],mx[i-1][pa[i-1][j]]);
            mi[i][j]=min(mi[i-1][j],mi[i-1][pa[i-1][j]]);
            mi2[i][j]=min(mi2[i-1][j],mi2[i-1][pa[i-1][j]]);
            mi3[i][j]=min(mi3[i-1][j],mi3[i-1][pa[i-1][j]]);
        }
    }
}
A LCA(int u,int v){
    int chu=0,chv=0;
    if(h[u]<h[v]) swap(u,v);
    int diff=h[u]-h[v],maxedge=-1,minout=2e9,i;
    /*if(h[u]==h[v]) minout=min(minout,mi[0][v]);
    minout=min(minout,mi[0][u]);*/
    for(i=0;i<20;i++){
        if((diff&(1<<i))!=0){
            if(chu==1) minout=min(mi2[i][u],minout);
            chu=1;
            maxedge=max(mx[i][u],maxedge);
            u=pa[i][u];
        } ;
    }
    if(u==v) return {u,maxedge,minout};
    for(i=19;i>=0;i--){
        if(pa[i][u]!=pa[i][v]){
            maxedge=max(mx[i][u],maxedge);
            if(chu==1) minout=min(mi2[i][u],minout);
            maxedge=max(mx[i][v],maxedge);
            if(chv==1) minout=min(mi2[i][v],minout);
            u=pa[i][u];
            v=pa[i][v];
            chu=1;
            chv=1;
        }
    }
    maxedge=max(mx[0][u],maxedge);
    if(chu==1) minout=min(mi2[0][u],minout);
    maxedge=max(mx[0][v],maxedge);
    if(chv==1) minout=min(mi2[0][v],minout);
    return {pa[0][u],maxedge,minout};
}
int getMinimumFuelCapacity(int X, int Y) {
    cnt++;
    A all=LCA(X,Y);
    int lca=all.u,maxedge=all.v,minout=all.w;
    if(lca!=X&&lca!=Y){
        minout=min(minout,mi3[0][lca]);
        if(lca!=0) minout=min(minout,mx[0][lca]);
    }
    if(max(maxedge,minout)>1e9) return -1;
    return max(maxedge,minout);
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2

*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Correct 19 ms 37064 KB Output is correct
4 Correct 21 ms 37256 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 17 ms 37452 KB Output is correct
8 Correct 17 ms 37376 KB Output is correct
9 Correct 133 ms 57524 KB Output is correct
10 Correct 177 ms 64328 KB Output is correct
11 Correct 145 ms 62992 KB Output is correct
12 Correct 149 ms 64940 KB Output is correct
13 Correct 148 ms 67736 KB Output is correct
14 Correct 154 ms 56648 KB Output is correct
15 Correct 456 ms 65680 KB Output is correct
16 Correct 493 ms 62500 KB Output is correct
17 Correct 418 ms 69524 KB Output is correct
18 Correct 423 ms 67236 KB Output is correct
19 Incorrect 112 ms 44356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Incorrect 207 ms 56864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Correct 19 ms 37064 KB Output is correct
4 Correct 21 ms 37256 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 17 ms 37452 KB Output is correct
8 Correct 17 ms 37376 KB Output is correct
9 Incorrect 17 ms 37196 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 37196 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Correct 19 ms 37064 KB Output is correct
4 Correct 21 ms 37256 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 17 ms 37452 KB Output is correct
8 Correct 17 ms 37376 KB Output is correct
9 Correct 133 ms 57524 KB Output is correct
10 Correct 177 ms 64328 KB Output is correct
11 Correct 145 ms 62992 KB Output is correct
12 Correct 149 ms 64940 KB Output is correct
13 Correct 148 ms 67736 KB Output is correct
14 Correct 154 ms 56648 KB Output is correct
15 Correct 456 ms 65680 KB Output is correct
16 Correct 493 ms 62500 KB Output is correct
17 Correct 418 ms 69524 KB Output is correct
18 Correct 423 ms 67236 KB Output is correct
19 Incorrect 207 ms 56864 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 37196 KB Output isn't correct