oj.uz

Submission #403592

# Submission time Handle Problem Language Result Execution time Memory
403592 2021-05-13T09:52:09 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
0 / 100
 643 ms 69544 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;
    for(i=0;i<20;i++){
        if((diff&(1<<i))!=0){
            minout=min(mi2[i][u],minout);
            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);
            minout=min(mi2[i][u],minout);
            maxedge=max(mx[i][v],maxedge);
            minout=min(mi2[i][v],minout);
            u=pa[i][u];
            v=pa[i][v];
        }
    }
    maxedge=max(mx[0][u],maxedge);
    minout=min(mi2[0][u],minout);
    maxedge=max(mx[0][v],maxedge);
    minout=min(mi2[0][v],minout);
    return {pa[0][u],maxedge,minout};
}
int getMinimumFuelCapacity(int X, int Y) {
    cnt++;
    int lca,maxedge,minout,me2,mi2;
    A all=LCA(X,Y);
    lca=all.u,maxedge=all.v,minout=all.w;
    if(lca==X){
        all=LCA(X,pa[0][Y]);
    }else if(lca==Y){
        all=LCA(Y,pa[0][X]);
    }else{
        all=LCA(pa[0][Y],pa[0][X]);
    }
    lca=all.u,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

*/

Compilation message

swap.cpp: In function 'A LCA(int, int)':
swap.cpp:87:9: warning: unused variable 'chu' [-Wunused-variable]
   87 |     int chu=0,chv=0;
      |         ^~~
swap.cpp:87:15: warning: unused variable 'chv' [-Wunused-variable]
   87 |     int chu=0,chv=0;
      |               ^~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:116:28: warning: unused variable 'me2' [-Wunused-variable]
  116 |     int lca,maxedge,minout,me2,mi2;
      |                            ^~~
swap.cpp:116:32: warning: unused variable 'mi2' [-Wunused-variable]
  116 |     int lca,maxedge,minout,me2,mi2;
      |                                ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 20 ms 37192 KB Output is correct
3 Correct 16 ms 37196 KB Output is correct
4 Correct 17 ms 37200 KB Output is correct
5 Correct 18 ms 37324 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 18 ms 37324 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 114 ms 57520 KB Output is correct
10 Correct 148 ms 64248 KB Output is correct
11 Correct 137 ms 63040 KB Output is correct
12 Correct 144 ms 64936 KB Output is correct
13 Correct 127 ms 67880 KB Output is correct
14 Correct 164 ms 56688 KB Output is correct
15 Correct 550 ms 65744 KB Output is correct
16 Correct 643 ms 62632 KB Output is correct
17 Correct 428 ms 69544 KB Output is correct
18 Correct 537 ms 67240 KB Output is correct
19 Incorrect 144 ms 44452 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 20 ms 37192 KB Output is correct
3 Incorrect 230 ms 56900 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 20 ms 37192 KB Output is correct
3 Correct 16 ms 37196 KB Output is correct
4 Correct 17 ms 37200 KB Output is correct
5 Correct 18 ms 37324 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 18 ms 37324 KB Output is correct
8 Correct 18 ms 37452 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 20 ms 37192 KB Output is correct
3 Correct 16 ms 37196 KB Output is correct
4 Correct 17 ms 37200 KB Output is correct
5 Correct 18 ms 37324 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 18 ms 37324 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 114 ms 57520 KB Output is correct
10 Correct 148 ms 64248 KB Output is correct
11 Correct 137 ms 63040 KB Output is correct
12 Correct 144 ms 64936 KB Output is correct
13 Correct 127 ms 67880 KB Output is correct
14 Correct 164 ms 56688 KB Output is correct
15 Correct 550 ms 65744 KB Output is correct
16 Correct 643 ms 62632 KB Output is correct
17 Correct 428 ms 69544 KB Output is correct
18 Correct 537 ms 67240 KB Output is correct
19 Incorrect 230 ms 56900 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