oj.uz

Submission #403620

# Submission time Handle Problem Language Result Execution time Memory
403620 2021-05-13T10:13:37 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
6 / 100
 211 ms 69524 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,maxall;
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]};
        maxall=max(maxall,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(n==m) return maxall;
    return -1;
    /*if(X==0||Y==0) return -1;
    if(m<=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:88:9: warning: unused variable 'chu' [-Wunused-variable]
   88 |     int chu=0,chv=0;
      |         ^~~
swap.cpp:88:15: warning: unused variable 'chv' [-Wunused-variable]
   88 |     int chu=0,chv=0;
      |               ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 18 ms 37196 KB Output is correct
3 Correct 17 ms 37112 KB Output is correct
4 Correct 17 ms 37192 KB Output is correct
5 Correct 17 ms 37412 KB Output is correct
6 Correct 18 ms 37376 KB Output is correct
7 Correct 17 ms 37320 KB Output is correct
8 Correct 18 ms 37404 KB Output is correct
9 Correct 110 ms 57632 KB Output is correct
10 Correct 135 ms 64252 KB Output is correct
11 Correct 135 ms 63044 KB Output is correct
12 Correct 143 ms 64964 KB Output is correct
13 Correct 137 ms 67876 KB Output is correct
14 Correct 117 ms 56620 KB Output is correct
15 Correct 201 ms 65692 KB Output is correct
16 Correct 196 ms 62484 KB Output is correct
17 Correct 202 ms 69524 KB Output is correct
18 Correct 186 ms 67336 KB Output is correct
19 Correct 84 ms 45488 KB Output is correct
20 Correct 194 ms 65984 KB Output is correct
21 Correct 191 ms 63780 KB Output is correct
22 Correct 211 ms 67368 KB Output is correct
23 Correct 188 ms 67980 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 18 ms 37196 KB Output is correct
3 Incorrect 142 ms 55492 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 18 ms 37196 KB Output is correct
3 Correct 17 ms 37112 KB Output is correct
4 Correct 17 ms 37192 KB Output is correct
5 Correct 17 ms 37412 KB Output is correct
6 Correct 18 ms 37376 KB Output is correct
7 Correct 17 ms 37320 KB Output is correct
8 Correct 18 ms 37404 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 18 ms 37196 KB Output is correct
3 Correct 17 ms 37112 KB Output is correct
4 Correct 17 ms 37192 KB Output is correct
5 Correct 17 ms 37412 KB Output is correct
6 Correct 18 ms 37376 KB Output is correct
7 Correct 17 ms 37320 KB Output is correct
8 Correct 18 ms 37404 KB Output is correct
9 Correct 110 ms 57632 KB Output is correct
10 Correct 135 ms 64252 KB Output is correct
11 Correct 135 ms 63044 KB Output is correct
12 Correct 143 ms 64964 KB Output is correct
13 Correct 137 ms 67876 KB Output is correct
14 Correct 117 ms 56620 KB Output is correct
15 Correct 201 ms 65692 KB Output is correct
16 Correct 196 ms 62484 KB Output is correct
17 Correct 202 ms 69524 KB Output is correct
18 Correct 186 ms 67336 KB Output is correct
19 Incorrect 142 ms 55492 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