제출 #872071

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

factories

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

using namespace std;

typedef pair<int, long long> pii;

const int N = 500'000 + 7;
vector<pii> adj[N];
int n;
long long a[N], b[N];
bool x[N], y[N];

void Init(int N, int A[], int B[], int D[]) {
    assert(false);
    n = N;
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
}

void dfs(int v, int p) {
    if (x[v])
        a[v] = 0;
    if (y[v])
        b[v] = 0;

    for (auto [u, w] : adj[v])
        if (u != p) {
            a[v] = min(a[v], a[u] + w);
            b[v] = min(b[v], b[u] + w);

            dfs(u, v);
        }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < n; i++)
        x[i] = y[i] = false, a[i] = b[i] = 1e18;
    for (int i = 0; i < S; i++)
        x[X[i]] = true;
    for (int i = 0; i < T; i++)
        y[Y[i]] = true;

    dfs(0, 0);
    long long res = 1e18;
    for (int i = 0; i < n; i++)
        res = min(res, a[i] + b[i]);
    return res;
}

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