oj.uz

Submission #403513

# Submission time Handle Problem Language Result Execution time Memory
403513 2021-05-13T09:02:36 Z Waratpp123 Swapping Cities (APIO20_swap) C++14
0 / 100
 214 ms 47664 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],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(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]=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){
            mi[0][j]=min(mi[0][j],g2[j][1].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]=max(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]]);
        }
    }
}
A LCA(int u,int v){
    if(h[u]<h[v]) swap(u,v);
    int diff=h[u]-h[v],maxedge=-1,minout=2e9,i;
    if(h[u]==h[v]) minout=min(minout,mi[0][v]);
    minout=min(minout,mi[0][u]);
    for(i=0;i<20;i++){
        if((diff&(1<<i))!=0) maxedge=max(mx[i][u],maxedge),minout=min(mi2[i][u],minout),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) {
    int i,j,ch=0,u,v;
    cnt++;
    A all=LCA(X,Y);
    int lca=all.u,maxedge=all.v,minout=all.w;
    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 'int getMinimumFuelCapacity(int, int)':
swap.cpp:104:9: warning: unused variable 'i' [-Wunused-variable]
  104 |     int i,j,ch=0,u,v;
      |         ^
swap.cpp:104:11: warning: unused variable 'j' [-Wunused-variable]
  104 |     int i,j,ch=0,u,v;
      |           ^
swap.cpp:104:13: warning: unused variable 'ch' [-Wunused-variable]
  104 |     int i,j,ch=0,u,v;
      |             ^~
swap.cpp:104:18: warning: unused variable 'u' [-Wunused-variable]
  104 |     int i,j,ch=0,u,v;
      |                  ^
swap.cpp:104:20: warning: unused variable 'v' [-Wunused-variable]
  104 |     int i,j,ch=0,u,v;
      |                    ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29260 KB Output is correct
2 Correct 15 ms 29340 KB Output is correct
3 Incorrect 14 ms 29364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29260 KB Output is correct
2 Correct 15 ms 29340 KB Output is correct
3 Incorrect 214 ms 47664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29260 KB Output is correct
2 Correct 15 ms 29340 KB Output is correct
3 Incorrect 14 ms 29364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29260 KB Output is correct
2 Correct 15 ms 29340 KB Output is correct
3 Incorrect 14 ms 29364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29260 KB Output is correct
2 Correct 15 ms 29340 KB Output is correct
3 Incorrect 14 ms 29364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29260 KB Output is correct
2 Correct 15 ms 29340 KB Output is correct
3 Incorrect 14 ms 29364 KB Output isn't correct
4 Halted 0 ms 0 KB -