oj.uz

Submission #403608

# Submission time Handle Problem Language Result Execution time Memory
403608 2021-05-13T10:03:55 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
0 / 100
 215 ms 69516 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(max(mi3[0][0],max(mx[0][X],mx[0][Y]))>1e9) return -1;
    return max(mi3[0][0],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;
      |               ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37196 KB Output is correct
2 Correct 17 ms 37196 KB Output is correct
3 Correct 17 ms 37196 KB Output is correct
4 Correct 17 ms 37224 KB Output is correct
5 Correct 17 ms 37324 KB Output is correct
6 Correct 18 ms 37376 KB Output is correct
7 Correct 18 ms 37408 KB Output is correct
8 Correct 17 ms 37400 KB Output is correct
9 Correct 118 ms 57620 KB Output is correct
10 Correct 137 ms 64248 KB Output is correct
11 Correct 142 ms 63072 KB Output is correct
12 Correct 145 ms 64968 KB Output is correct
13 Correct 129 ms 67800 KB Output is correct
14 Correct 122 ms 56644 KB Output is correct
15 Correct 197 ms 65744 KB Output is correct
16 Correct 203 ms 62504 KB Output is correct
17 Correct 215 ms 69516 KB Output is correct
18 Correct 197 ms 67216 KB Output is correct
19 Incorrect 82 ms 44320 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37196 KB Output is correct
2 Correct 17 ms 37196 KB Output is correct
3 Incorrect 149 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 19 ms 37196 KB Output is correct
2 Correct 17 ms 37196 KB Output is correct
3 Correct 17 ms 37196 KB Output is correct
4 Correct 17 ms 37224 KB Output is correct
5 Correct 17 ms 37324 KB Output is correct
6 Correct 18 ms 37376 KB Output is correct
7 Correct 18 ms 37408 KB Output is correct
8 Correct 17 ms 37400 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 19 ms 37196 KB Output is correct
2 Correct 17 ms 37196 KB Output is correct
3 Correct 17 ms 37196 KB Output is correct
4 Correct 17 ms 37224 KB Output is correct
5 Correct 17 ms 37324 KB Output is correct
6 Correct 18 ms 37376 KB Output is correct
7 Correct 18 ms 37408 KB Output is correct
8 Correct 17 ms 37400 KB Output is correct
9 Correct 118 ms 57620 KB Output is correct
10 Correct 137 ms 64248 KB Output is correct
11 Correct 142 ms 63072 KB Output is correct
12 Correct 145 ms 64968 KB Output is correct
13 Correct 129 ms 67800 KB Output is correct
14 Correct 122 ms 56644 KB Output is correct
15 Correct 197 ms 65744 KB Output is correct
16 Correct 203 ms 62504 KB Output is correct
17 Correct 215 ms 69516 KB Output is correct
18 Correct 197 ms 67216 KB Output is correct
19 Incorrect 149 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