제출 #1031045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031045		PVSekhar	공장들 (JOI14_factories)	C++14	100 / 100	3301 ms	367892 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std; 
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 5e5 + 2;
const ll INF = 1e14 + 2;

vector<ll> dist(N);
vector<int> sz(N), is_dead(N, 0);
vector<vector<pair<int, ll>>> edges(N), cent(N);

int n;
void find_sz(int node, int parent) {
    sz[node] = 1;
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        find_sz(child.first, node);
        sz[node] += sz[child.first];
    }
}

void update(int node, int parent, int c, ll d) {
    cent[node].push_back(make_pair(c, d));
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        update(child.first, node, c, d + child.second);
    }
}

void find_cent(int node, int parent, int size) {
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        if (sz[child.first] * 2 > size) {
            find_cent(child.first, node, size);
            return;
        }
    }
    update(node, -1, node, 0);
    is_dead[node] = 1;
    find_sz(node, -1);
    for (auto child :edges[node]) {
        if (is_dead[child.first]) continue;
        find_cent(child.first, node, sz[child.first]);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; i++) {
        edges[A[i]].push_back(make_pair(B[i], D[i]));
        edges[B[i]].push_back(make_pair(A[i], D[i]));
    }
    find_sz(0, -1);
    find_cent(0, -1, N);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        for (auto p : cent[Y[i]]) {
            dist[p.first] = INF;
        }
    }
    for (int i = 0; i < S; i++) {
        for (auto p : cent[X[i]]) {
            dist[p.first] = min(dist[p.first], p.second);
        }
    }
    for (int i = 0; i < T; i++) {
        for (auto p : cent[Y[i]]) {
            ans = min(ans, dist[p.first] + p.second);
        }
    }
    return ans;
}

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