oj.uz

Submission #403616

# Submission time Handle Problem Language Result Execution time Memory
403616 2021-05-13T10:08:52 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
0 / 100
 212 ms 69480 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);*/
    if(X==0||Y==0) return -1;
    if(g2[0].size()<=2) return -1;
    for(auto x : g2[0]){
        if(x.u!=X&&x.u!=Y) return x.w;
    }
}
/*
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:138:1: warning: control reaches end of non-void function [-Wreturn-type]
  138 | }
      | ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37152 KB Output is correct
2 Correct 17 ms 37100 KB Output is correct
3 Correct 17 ms 37196 KB Output is correct
4 Correct 19 ms 37324 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 18 ms 37404 KB Output is correct
8 Correct 19 ms 37488 KB Output is correct
9 Correct 113 ms 57540 KB Output is correct
10 Correct 136 ms 64320 KB Output is correct
11 Correct 135 ms 63080 KB Output is correct
12 Correct 140 ms 64924 KB Output is correct
13 Correct 128 ms 67748 KB Output is correct
14 Correct 115 ms 56604 KB Output is correct
15 Correct 206 ms 65872 KB Output is correct
16 Correct 194 ms 62532 KB Output is correct
17 Correct 212 ms 69480 KB Output is correct
18 Correct 195 ms 67348 KB Output is correct
19 Incorrect 81 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 37152 KB Output is correct
2 Correct 17 ms 37100 KB Output is correct
3 Incorrect 148 ms 55948 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 37152 KB Output is correct
2 Correct 17 ms 37100 KB Output is correct
3 Correct 17 ms 37196 KB Output is correct
4 Correct 19 ms 37324 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 18 ms 37404 KB Output is correct
8 Correct 19 ms 37488 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 37152 KB Output is correct
2 Correct 17 ms 37100 KB Output is correct
3 Correct 17 ms 37196 KB Output is correct
4 Correct 19 ms 37324 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 18 ms 37404 KB Output is correct
8 Correct 19 ms 37488 KB Output is correct
9 Correct 113 ms 57540 KB Output is correct
10 Correct 136 ms 64320 KB Output is correct
11 Correct 135 ms 63080 KB Output is correct
12 Correct 140 ms 64924 KB Output is correct
13 Correct 128 ms 67748 KB Output is correct
14 Correct 115 ms 56604 KB Output is correct
15 Correct 206 ms 65872 KB Output is correct
16 Correct 194 ms 62532 KB Output is correct
17 Correct 212 ms 69480 KB Output is correct
18 Correct 195 ms 67348 KB Output is correct
19 Incorrect 148 ms 55948 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