제출 #993772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993772		Peti	공장들 (JOI14_factories)	C++17	0 / 100	5 ms	884 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

int n;
const long long INF = 1e18;

vector<vector<pair<int, long long>>> g, cp;
vector<bool> vis;
vector<int> g_sz;

vector<long long> min_dist;

int dfs_sz(int x, int p = -1){
    g_sz[x] = 1;
    for(auto [y, _] : g[x]){
        if(y != p && !vis[y]){
            g_sz[x] += dfs_sz(y, x);
        }
    }
    return g_sz[x];
}

int dfs_c(int x, int sz, int p = -1){
    for(auto [y, _] : g[x]){
        if(y != p && !vis[y] && g_sz[y]*2 > sz){
            return dfs_c(y, sz, x);
        }
    }
    return x;
}

void dfs(int x, long long d, int c, int p = -1){
    cp[x].emplace_back(c, d);
    for(auto [y, w] : g[x]){
        if(y != p && !vis[y]){
            dfs(y, d + w, c, x);
        }
    }
}

void centroid_decomp(int x){
    int c = dfs_c(x, dfs_sz(x));
    dfs(c, 0, c);
    vis[c] = true;

    for(auto [y, _] : g[x]){
        if(!vis[y]){
            centroid_decomp(y);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
    g.assign(n, vector<pair<int, long long>>());
    cp.assign(n, vector<pair<int, long long>>());
    vis.assign(n, false);
    min_dist.assign(n, INF);
    g_sz.assign(n, 0);

    for(int i = 0; i < N; i++){
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }

    centroid_decomp(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> q;
    for(int i = 0; i < S; i++){
        int x = X[i];
        for(auto [y, d] : cp[x]){
            min_dist[y] = min(min_dist[y], d);
            q.push_back(y);
        }
    }

    long long ans = INF;
    for(int i = 0; i < T; i++){
        int x = Y[i];
        for(auto [y, d] : cp[x]){
            ans = min(ans, min_dist[y] + d);
        }
    }
    
    for(int x : q) min_dist[x] = INF;

	return ans;
}

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