제출 #1223393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223393		colossal_pepe	공장들 (JOI14_factories)	C++20	0 / 100	8090 ms	49952 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 1e18;

int n;
vector<vector<pair<int, ll>>> g;

ll dfs(int u, int par, vector<bool> &imp) {
	if (imp[u]) return 0;
	ll ret = INF;
	for (pair<int, ll> v : g[u]) {
		if (v.first == par) continue;
		ret = min(ret, v.second + dfs(v.first, u, imp));
	}
	return ret;
}

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

ll Query(int S, int X[], int T, int Y[]) {
	if (n > 5000) return -1;
	vector<bool> imp(n, 0);
	for (int i = 0; i < T; i++) {
		imp[Y[i]] = 1;
	}
	ll ans = INF;
	for (int i = 0; i < S; i++) {
		ans = min(ans, dfs(X[i], -1, imp));
	}
	return ans;
}

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