oj.uz

Submission #403604

# Submission time Handle Problem Language Result Execution time Memory
403604 2021-05-13T10:00:44 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
0 / 100
 637 ms 69548 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;
    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;
      |               ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37196 KB Output is correct
2 Correct 18 ms 37212 KB Output is correct
3 Correct 18 ms 37156 KB Output is correct
4 Correct 20 ms 37324 KB Output is correct
5 Correct 22 ms 37324 KB Output is correct
6 Correct 18 ms 37368 KB Output is correct
7 Correct 18 ms 37332 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 114 ms 57644 KB Output is correct
10 Correct 142 ms 64324 KB Output is correct
11 Correct 174 ms 63044 KB Output is correct
12 Correct 152 ms 65068 KB Output is correct
13 Correct 137 ms 67928 KB Output is correct
14 Correct 191 ms 56628 KB Output is correct
15 Correct 569 ms 65768 KB Output is correct
16 Correct 637 ms 62576 KB Output is correct
17 Correct 415 ms 69548 KB Output is correct
18 Correct 582 ms 67352 KB Output is correct
19 Incorrect 148 ms 44308 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37196 KB Output is correct
2 Correct 18 ms 37212 KB Output is correct
3 Incorrect 244 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 18 ms 37196 KB Output is correct
2 Correct 18 ms 37212 KB Output is correct
3 Correct 18 ms 37156 KB Output is correct
4 Correct 20 ms 37324 KB Output is correct
5 Correct 22 ms 37324 KB Output is correct
6 Correct 18 ms 37368 KB Output is correct
7 Correct 18 ms 37332 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Incorrect 17 ms 37124 KB Output isn't correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37196 KB Output is correct
2 Correct 18 ms 37212 KB Output is correct
3 Correct 18 ms 37156 KB Output is correct
4 Correct 20 ms 37324 KB Output is correct
5 Correct 22 ms 37324 KB Output is correct
6 Correct 18 ms 37368 KB Output is correct
7 Correct 18 ms 37332 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 114 ms 57644 KB Output is correct
10 Correct 142 ms 64324 KB Output is correct
11 Correct 174 ms 63044 KB Output is correct
12 Correct 152 ms 65068 KB Output is correct
13 Correct 137 ms 67928 KB Output is correct
14 Correct 191 ms 56628 KB Output is correct
15 Correct 569 ms 65768 KB Output is correct
16 Correct 637 ms 62576 KB Output is correct
17 Correct 415 ms 69548 KB Output is correct
18 Correct 582 ms 67352 KB Output is correct
19 Incorrect 244 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 37124 KB Output isn't correct