oj.uz

Submission #403618

# Submission time Handle Problem Language Result Execution time Memory
403618 2021-05-13T10:11:12 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
0 / 100
 262 ms 69648 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 max(x.w,max(mx[0][X],mx[0][Y]));
    }
}
/*
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 37156 KB Output is correct
2 Correct 16 ms 37192 KB Output is correct
3 Correct 20 ms 37164 KB Output is correct
4 Correct 20 ms 37324 KB Output is correct
5 Correct 18 ms 37360 KB Output is correct
6 Correct 18 ms 37320 KB Output is correct
7 Correct 18 ms 37368 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 112 ms 57576 KB Output is correct
10 Correct 177 ms 64244 KB Output is correct
11 Correct 135 ms 62992 KB Output is correct
12 Correct 150 ms 64908 KB Output is correct
13 Correct 133 ms 67760 KB Output is correct
14 Correct 116 ms 56692 KB Output is correct
15 Correct 208 ms 65776 KB Output is correct
16 Correct 199 ms 62492 KB Output is correct
17 Correct 262 ms 69648 KB Output is correct
18 Correct 195 ms 67244 KB Output is correct
19 Incorrect 81 ms 44460 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 37156 KB Output is correct
2 Correct 16 ms 37192 KB Output is correct
3 Incorrect 195 ms 56860 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 37156 KB Output is correct
2 Correct 16 ms 37192 KB Output is correct
3 Correct 20 ms 37164 KB Output is correct
4 Correct 20 ms 37324 KB Output is correct
5 Correct 18 ms 37360 KB Output is correct
6 Correct 18 ms 37320 KB Output is correct
7 Correct 18 ms 37368 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Incorrect 17 ms 37204 KB Output isn't correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37156 KB Output is correct
2 Correct 16 ms 37192 KB Output is correct
3 Correct 20 ms 37164 KB Output is correct
4 Correct 20 ms 37324 KB Output is correct
5 Correct 18 ms 37360 KB Output is correct
6 Correct 18 ms 37320 KB Output is correct
7 Correct 18 ms 37368 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 112 ms 57576 KB Output is correct
10 Correct 177 ms 64244 KB Output is correct
11 Correct 135 ms 62992 KB Output is correct
12 Correct 150 ms 64908 KB Output is correct
13 Correct 133 ms 67760 KB Output is correct
14 Correct 116 ms 56692 KB Output is correct
15 Correct 208 ms 65776 KB Output is correct
16 Correct 199 ms 62492 KB Output is correct
17 Correct 262 ms 69648 KB Output is correct
18 Correct 195 ms 67244 KB Output is correct
19 Incorrect 195 ms 56860 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 37204 KB Output isn't correct