oj.uz

답안 #883596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883596 2023-12-05T13:35:56 Z Warinchai 공장들 (JOI14_factories) C++14
0 / 100
 21 ms 74324 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long> >adj[500005];
int sz[500005];
bool used[500005];
long long pl[20][500005];
int pa[500005];
int lv[500005];
long long mn[500005];
int dfssz(int u,int p=-1){
    sz[u]=1;
    for(auto v:adj[u])if(v.first!=p&&!used[v.first])sz[u]+=dfssz(v.first,u);
    return sz[u];
}
int centroid(int u,int rsz,int p=-1){
    for(auto v:adj[u])if(v.first!=p&&!used[v.first]&&sz[v.first]>rsz/2)return centroid(v.first,rsz,u);
    return u;
}
void dfs(int u,long long d,int lvl,int p=-1){
    pl[lvl][u]=d;
    for(auto v:adj[u])if(v.first!=p&&!used[v.first])dfs(v.first,d+v.second,lvl+1,u);
}
void decom(int u,int lvl,int p=-1){
    u=centroid(u,dfssz(u));
    pa[u]=p;
    lv[u]=lvl;
    used[u]=true;
    dfs(u,0,lvl);
    for(auto v:adj[u])if(v.first!=p&&!used[v.first])decom(v.first,lvl+1,u);
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N;i++)adj[B[i]].push_back({A[i],D[i]}),adj[A[i]].push_back({B[i],D[i]});
    decom(1,1);
    for(int i=0;i<=N;i++)mn[i]=LLONG_MAX;
}
long long fans(int x){
    long long ans=LLONG_MAX;
    while(x!=-1){
        ans=min(ans,mn[x]);
        x=pa[x];
    }
    return ans;
}
void upd(int x){
    int st=x;
    while(x!=-1){
        mn[x]=min(mn[x],pl[lv[x]][st]);
        x=pa[x];
    }
}
void rvupd(int x){
    while(x!=-1){
        mn[x]=LLONG_MAX;
        x=pa[x];
    }
}
long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<S;i++)upd(X[i]);
    long long ans=LLONG_MAX;
    for(int i=0;i<T;i++)ans=min(ans,fans(Y[i]));
    for(int i=0;i<S;i++)rvupd(X[i]);
    return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 74324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 68188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 74324 KB Output isn't correct
2 Halted 0 ms 0 KB -