oj.uz

답안 #403562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403562 2021-05-13T09:32:56 Z Waratpp123 자매 도시 (APIO20_swap) C++14
0 / 100
 437 ms 72796 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){
    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) {
    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 37196 KB Output is correct
3 Correct 17 ms 37144 KB Output is correct
4 Correct 17 ms 37268 KB Output is correct
5 Correct 18 ms 37452 KB Output is correct
6 Correct 18 ms 37436 KB Output is correct
7 Correct 18 ms 37436 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 129 ms 59284 KB Output is correct
10 Correct 159 ms 66272 KB Output is correct
11 Correct 155 ms 64984 KB Output is correct
12 Correct 158 ms 67040 KB Output is correct
13 Correct 135 ms 69928 KB Output is correct
14 Correct 148 ms 58524 KB Output is correct
15 Correct 419 ms 69116 KB Output is correct
16 Correct 437 ms 65780 KB Output is correct
17 Correct 406 ms 72796 KB Output is correct
18 Correct 413 ms 70936 KB Output is correct
19 Incorrect 112 ms 46276 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 37196 KB Output is correct
3 Incorrect 239 ms 58276 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 37196 KB Output is correct
3 Correct 17 ms 37144 KB Output is correct
4 Correct 17 ms 37268 KB Output is correct
5 Correct 18 ms 37452 KB Output is correct
6 Correct 18 ms 37436 KB Output is correct
7 Correct 18 ms 37436 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 17 ms 37196 KB Output is correct
10 Correct 18 ms 37324 KB Output is correct
11 Correct 18 ms 37356 KB Output is correct
12 Correct 19 ms 37324 KB Output is correct
13 Correct 18 ms 37276 KB Output is correct
14 Correct 18 ms 37336 KB Output is correct
15 Incorrect 19 ms 37436 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 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 37144 KB Output is correct
5 Correct 17 ms 37268 KB Output is correct
6 Correct 18 ms 37452 KB Output is correct
7 Correct 18 ms 37436 KB Output is correct
8 Correct 18 ms 37436 KB Output is correct
9 Correct 18 ms 37452 KB Output is correct
10 Correct 129 ms 59284 KB Output is correct
11 Correct 159 ms 66272 KB Output is correct
12 Correct 155 ms 64984 KB Output is correct
13 Correct 158 ms 67040 KB Output is correct
14 Correct 135 ms 69928 KB Output is correct
15 Correct 18 ms 37324 KB Output is correct
16 Correct 18 ms 37356 KB Output is correct
17 Correct 19 ms 37324 KB Output is correct
18 Correct 18 ms 37276 KB Output is correct
19 Correct 18 ms 37336 KB Output is correct
20 Incorrect 19 ms 37436 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 37196 KB Output is correct
2 Correct 17 ms 37196 KB Output is correct
3 Correct 17 ms 37144 KB Output is correct
4 Correct 17 ms 37268 KB Output is correct
5 Correct 18 ms 37452 KB Output is correct
6 Correct 18 ms 37436 KB Output is correct
7 Correct 18 ms 37436 KB Output is correct
8 Correct 18 ms 37452 KB Output is correct
9 Correct 129 ms 59284 KB Output is correct
10 Correct 159 ms 66272 KB Output is correct
11 Correct 155 ms 64984 KB Output is correct
12 Correct 158 ms 67040 KB Output is correct
13 Correct 135 ms 69928 KB Output is correct
14 Correct 148 ms 58524 KB Output is correct
15 Correct 419 ms 69116 KB Output is correct
16 Correct 437 ms 65780 KB Output is correct
17 Correct 406 ms 72796 KB Output is correct
18 Correct 413 ms 70936 KB Output is correct
19 Incorrect 239 ms 58276 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 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 37144 KB Output is correct
5 Correct 17 ms 37268 KB Output is correct
6 Correct 18 ms 37452 KB Output is correct
7 Correct 18 ms 37436 KB Output is correct
8 Correct 18 ms 37436 KB Output is correct
9 Correct 18 ms 37452 KB Output is correct
10 Correct 129 ms 59284 KB Output is correct
11 Correct 159 ms 66272 KB Output is correct
12 Correct 155 ms 64984 KB Output is correct
13 Correct 158 ms 67040 KB Output is correct
14 Correct 135 ms 69928 KB Output is correct
15 Correct 148 ms 58524 KB Output is correct
16 Correct 419 ms 69116 KB Output is correct
17 Correct 437 ms 65780 KB Output is correct
18 Correct 406 ms 72796 KB Output is correct
19 Correct 413 ms 70936 KB Output is correct
20 Incorrect 239 ms 58276 KB Output isn't correct
21 Halted 0 ms 0 KB -