Submission #222929

#	Time	Username	Problem	Language	Result	Execution time	Memory
222929		mhy908	Factories (JOI14_factories)	C++14	100 / 100	6483 ms	370380 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=1987654321987654321;
pil arr[500010];
int n, qq, sz[500010];
vector<pil> link[500010], up[500010];
bool ch[500010];
void dfs(int num, int par){
    sz[num]=1;
    for(auto i:link[num]){
        if(i.F==par||ch[i.F])continue;
        dfs(i.F, num);
        sz[num]+=sz[i.F];
    }
}
int get_centroid(int num, int par, int nd){
    for(auto i:link[num]){
        if(!ch[i.F]&&par!=i.F&&sz[i.F]>nd)return get_centroid(i.F, num, nd);
    }
    return num;
}
void get_up(int rt, int num, int par, LL d){
    up[num].pb(mp(rt, d));
    for(auto i:link[num]){
        if(i.F!=par&&!ch[i.F])get_up(rt, i.F, num, d+i.S);
    }
}
void get_centroid_tree(int num){
    dfs(num, 0);
    int cen=get_centroid(num, 0, sz[num]/2);
    get_up(cen, cen, 0, 0);
    ch[cen]=true;
    for(auto i:link[cen]){
        if(!ch[i.F])get_centroid_tree(i.F);
    }
}
void Init(int N, int A[], int B[], int D[]){
	for(int i=0; i<N-1; i++){
		link[A[i]+1].pb(mp(B[i]+1, D[i]));
		link[B[i]+1].pb(mp(A[i]+1, D[i]));
	}
	get_centroid_tree(1);
}
LL Query(int S, int X[], int T, int Y[]){
    qq--;
    for(int i=0; i<S; i++){
        for(auto j:up[X[i]+1])arr[j.F]=min(arr[j.F], mp(qq, j.S));
    }
    LL ret=llinf;
    for(int i=0; i<T; i++){
        for(auto j:up[Y[i]+1]){
            if(arr[j.F].F==qq)ret=min(ret, arr[j.F].S+j.S);
        }
    }
    return ret;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67