oj.uz

답안 #403567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403567 2021-05-13T09:37:45 Z Waratpp123 자매 도시 (APIO20_swap) C++14
0 / 100
 493 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;
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;
    /*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){
            if(chu==1) minout=min(mi2[i][u],minout);
            chu=1;
            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);
            if(chu==1) minout=min(mi2[i][u],minout);
            maxedge=max(mx[i][v],maxedge);
            if(chv==1) minout=min(mi2[i][v],minout);
            u=pa[i][u];
            v=pa[i][v];
            chu=1;
            chv=1;
        }
    }
    maxedge=max(mx[0][u],maxedge);
    if(chu==1) minout=min(mi2[0][u],minout);
    maxedge=max(mx[0][v],maxedge);
    if(chv==1) minout=min(mi2[0][v],minout);
    return {pa[0][u],maxedge,minout};
}
int getMinimumFuelCapacity(int X, int Y) {
    cnt++;
    A all=LCA(X,Y);
    int lca=all.u,maxedge=all.v,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);
}
/*
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

*/

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Correct 19 ms 37064 KB Output is correct
4 Correct 21 ms 37256 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 17 ms 37452 KB Output is correct
8 Correct 17 ms 37376 KB Output is correct
9 Correct 133 ms 57524 KB Output is correct
10 Correct 177 ms 64328 KB Output is correct
11 Correct 145 ms 62992 KB Output is correct
12 Correct 149 ms 64940 KB Output is correct
13 Correct 148 ms 67736 KB Output is correct
14 Correct 154 ms 56648 KB Output is correct
15 Correct 456 ms 65680 KB Output is correct
16 Correct 493 ms 62500 KB Output is correct
17 Correct 418 ms 69524 KB Output is correct
18 Correct 423 ms 67236 KB Output is correct
19 Incorrect 112 ms 44356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Incorrect 207 ms 56864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Correct 19 ms 37064 KB Output is correct
4 Correct 21 ms 37256 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 17 ms 37452 KB Output is correct
8 Correct 17 ms 37376 KB Output is correct
9 Incorrect 17 ms 37196 KB Output isn't correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 37196 KB Output isn't correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37156 KB Output is correct
3 Correct 19 ms 37064 KB Output is correct
4 Correct 21 ms 37256 KB Output is correct
5 Correct 18 ms 37420 KB Output is correct
6 Correct 18 ms 37324 KB Output is correct
7 Correct 17 ms 37452 KB Output is correct
8 Correct 17 ms 37376 KB Output is correct
9 Correct 133 ms 57524 KB Output is correct
10 Correct 177 ms 64328 KB Output is correct
11 Correct 145 ms 62992 KB Output is correct
12 Correct 149 ms 64940 KB Output is correct
13 Correct 148 ms 67736 KB Output is correct
14 Correct 154 ms 56648 KB Output is correct
15 Correct 456 ms 65680 KB Output is correct
16 Correct 493 ms 62500 KB Output is correct
17 Correct 418 ms 69524 KB Output is correct
18 Correct 423 ms 67236 KB Output is correct
19 Incorrect 207 ms 56864 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 37196 KB Output isn't correct