답안 #88123 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88123	2018-12-03T21:22:00 Z	KCSC	공장들 (JOI14_factories)	C++14	100 / 100	7289 ms	334404 KB

factories

#ifndef HOME
	#include "factories.h"
#endif

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

const int LOG = 21;
const int DIM = 500005;

int lev[DIM], szt[DIM], par[DIM], rmq[DIM << 1][LOG], pwr[DIM << 1], pos[DIM];
long long dst[DIM], dp[DIM], aux[DIM][LOG]; vector<pair<int, int>> edg[DIM]; bool oki[DIM];

void dfs(int x, int f, int d) {
	static int nr = 0;
	dst[x] = dst[f] + d; rmq[++nr][0] = x;   
	lev[x] = lev[f] + 1; pos[x] = nr;
	for (auto &ed : edg[x]) {
		int y = ed.first, c = ed.second;
		if (y != f) {
			dfs(y, x, c); rmq[++nr][0] = x; } } } 

void getCentroid(int x, int f, int sz, int &c) {
	int mx = 0; szt[x] = 1;
	for (auto &ed : edg[x]) {
		int y = ed.first;
		if (!oki[y] and y != f) {
			getCentroid(y, x, sz, c); szt[x] += szt[y];
			mx = max(mx, szt[y]); } }
	mx = max(mx, sz - szt[x]);
	if (mx <= sz / 2) {	
		c = x; } }

void buildRmq(int n) {
	for (int i = 2; i <= n; ++i) {
		pwr[i] = pwr[i >> 1] + 1; }
	for (int k = 1; (1 << (k - 1)) < n; ++k) {
		for (int i = 1, j = (1 << (k - 1)) + 1; j <= n; ++i, ++j) {
			if (lev[rmq[i][k - 1]] < lev[rmq[j][k - 1]]) {
				rmq[i][k] = rmq[i][k - 1]; }
			else {
				rmq[i][k] = rmq[j][k - 1]; } } } }

inline int lca(int x, int y) {
	x = pos[x]; y = pos[y]; 
	if (x > y) {
		swap(x, y); }
	int p = pwr[y - x + 1];
	return lev[rmq[x][p]] < lev[rmq[y - (1 << p) + 1][p]] ? 
		rmq[x][p] : rmq[y - (1 << p) + 1][p]; }

inline long long getDist(int x, int y) {
	return dst[x] + dst[y] - (dst[lca(x, y)] << 1); }

void getTree(int x, int f, int sz) {
	getCentroid(x, f, sz, x); getCentroid(x, f, sz, x); 
	par[x] = f; dp[x] = (1LL << 60); oki[x] = true;
	for (auto &ed : edg[x]) {
		int y = ed.first;
		if (!oki[y]) {
			getTree(y, x, szt[y]); } } }

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 0; i < n - 1; ++i) {
		int x = ++a[i], y = ++b[i], c = d[i];
		edg[x].push_back(make_pair(y, c));
		edg[y].push_back(make_pair(x, c)); }
	dfs(1, 0, 0); buildRmq((n << 1) - 1); getTree(1, 0, n);
	for (int x = 1; x <= n; ++x) {
		for (int i = 0, y = x; y != 0; ++i, y = par[y]) {
			aux[x][i] = getDist(x, y); } } }

long long Query(int s, int a[], int t, int b[]) {
	long long ans = (1LL << 60);
	if (s > t) {
		swap(a, b); swap(s, t); }
	for (int i = 0; i < s; ++i) {
		for (int x = ++a[i], j = 0; x; ++j, x = par[x]) {
			dp[x] = min(dp[x], aux[a[i]][j]); } }
	for (int i = 0; i < t; ++i) {
		for (int x = ++b[i], j = 0; x; ++j, x = par[x]) {
			ans = min(ans, dp[x] + aux[b[i]][j]); } }
	for (int i = 0; i < s; ++i) {
		for (int x = a[i]; x; x = par[x]) {
			dp[x] = (1LL << 60); } }
	return ans; }

#ifdef HOME
int main(void) {
	freopen("factories.in", "r", stdin);
	freopen("factories.out", "w", stdout);
	int n, q; cin >> n >> q;
	int a[100], b[100], d[100];
	for (int i = 0; i < n - 1; ++i) {
		cin >> a[i] >> b[i] >> d[i]; }
	Init(n, a, b, d);
	while (q--) {
		int s, t; cin >> s >> t;
		for (int i = 0; i < s; ++i) {
			cin >> a[i]; }
		for (int i = 0; i < t; ++i) {
			cin >> b[i]; }
		cout << Query(s, a, t, b) << "\n"; }	
	return 0; }
#endif

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	12792 KB	Output is correct
2	Correct	353 ms	26060 KB	Output is correct
3	Correct	387 ms	26124 KB	Output is correct
4	Correct	346 ms	26236 KB	Output is correct
5	Correct	390 ms	26548 KB	Output is correct
6	Correct	287 ms	26548 KB	Output is correct
7	Correct	378 ms	26548 KB	Output is correct
8	Correct	347 ms	26548 KB	Output is correct
9	Correct	394 ms	26772 KB	Output is correct
10	Correct	293 ms	26772 KB	Output is correct
11	Correct	383 ms	26772 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	26772 KB	Output is correct
2	Correct	3160 ms	232068 KB	Output is correct
3	Correct	5918 ms	235632 KB	Output is correct
4	Correct	1622 ms	235632 KB	Output is correct
5	Correct	6907 ms	269704 KB	Output is correct
6	Correct	6019 ms	269704 KB	Output is correct
7	Correct	1236 ms	269704 KB	Output is correct
8	Correct	588 ms	269704 KB	Output is correct
9	Correct	1197 ms	269704 KB	Output is correct
10	Correct	1066 ms	269704 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	12792 KB	Output is correct
2	Correct	353 ms	26060 KB	Output is correct
3	Correct	387 ms	26124 KB	Output is correct
4	Correct	346 ms	26236 KB	Output is correct
5	Correct	390 ms	26548 KB	Output is correct
6	Correct	287 ms	26548 KB	Output is correct
7	Correct	378 ms	26548 KB	Output is correct
8	Correct	347 ms	26548 KB	Output is correct
9	Correct	394 ms	26772 KB	Output is correct
10	Correct	293 ms	26772 KB	Output is correct
11	Correct	383 ms	26772 KB	Output is correct
12	Correct	14 ms	26772 KB	Output is correct
13	Correct	3160 ms	232068 KB	Output is correct
14	Correct	5918 ms	235632 KB	Output is correct
15	Correct	1622 ms	235632 KB	Output is correct
16	Correct	6907 ms	269704 KB	Output is correct
17	Correct	6019 ms	269704 KB	Output is correct
18	Correct	1236 ms	269704 KB	Output is correct
19	Correct	588 ms	269704 KB	Output is correct
20	Correct	1197 ms	269704 KB	Output is correct
21	Correct	1066 ms	269704 KB	Output is correct
22	Correct	3438 ms	269704 KB	Output is correct
23	Correct	4089 ms	269704 KB	Output is correct
24	Correct	6155 ms	269704 KB	Output is correct
25	Correct	6355 ms	269704 KB	Output is correct
26	Correct	6357 ms	269704 KB	Output is correct
27	Correct	7289 ms	269704 KB	Output is correct
28	Correct	1551 ms	269704 KB	Output is correct
29	Correct	5105 ms	286628 KB	Output is correct
30	Correct	6254 ms	310188 KB	Output is correct
31	Correct	5699 ms	334404 KB	Output is correct
32	Correct	1266 ms	334404 KB	Output is correct
33	Correct	573 ms	334404 KB	Output is correct
34	Correct	930 ms	334404 KB	Output is correct
35	Correct	958 ms	334404 KB	Output is correct
36	Correct	1092 ms	334404 KB	Output is correct
37	Correct	1107 ms	334404 KB	Output is correct

답안 #88123

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 18.0 / 18.0

Subtask #3 67.0 / 67.0

Subtask #1
15.0 / 15.0

Subtask #2
18.0 / 18.0

Subtask #3
67.0 / 67.0