oj.uz

Submission #302720

# Submission time Handle Problem Language Result Execution time Memory
302720 2020-09-19T05:17:53 Z hexan Factories (JOI14_factories) C++14
100 / 100
 6079 ms 187756 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define x first
#define y second
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)

const int N = 5e5 + 1;
const int lg = 20;
vector<pair<int, int>> g[N];
int p[N];
ll d[lg][N], dth[N];
int root = -1;


void tata(int v, int pa, ll cu, int death) {
	d[death][v] = cu;
	for(auto to : g[v]) {
		if (to.x == pa || p[to.x] != -1) continue;
		tata(to.x, v, cu + to.y, death);
	}
}

int dfs(int v, int pa, int &c, int n) {
	int sz = 1;
	for(auto to : g[v]) {
		if (to.x == pa || p[to.x] != -1) continue;
		sz += dfs(to.x, v, c, n);
	}
	if (c == -1 && (sz * 2 >=  n || pa == -1))
		c = v;
	return sz;
}

void dec(int v, int n) {
	tata(v, -1, 0, dth[v]);
	for(auto to : g[v]) {
		if (p[to.x] == -1) {
			int nx = -1;
			dfs(to.x, -1, nx, n / 2);
			p[nx] = v;
			dth[nx] = dth[v] + 1;
			dec(nx, n / 2);
		}
	}
}

int n;
const ll INF = 1e18;
ll used[N], f[2][N];

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++) {
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	fill(p, p + N, -1);
	dfs(0, -1, root, n);
	p[root] = root;
	dec(root, N);
}


int timer = 0;

ll ans;

long long Query(int S, int X[], int T, int Y[]) {
	timer++;	
	ans = INF;
	for(int i : {0, 1}) {
		for(int j = 0; j < (i == 0 ? S : T); j++) {
			int x;
			if (!i) x = X[j];
			else x = Y[j];
			ll val = x, e = dth[x];
			while (1) {
				if (used[x] != timer) {
					used[x] = timer;
					f[0][x] = INF;
					f[1][x] = INF;
				}
				f[i][x] = min(f[i][x], d[e][val]);
				chkmin(ans, f[0][x] + f[1][x]);
				if (p[x] != x) {
					x = p[x];
					--e;
				} else {
					break;
				}
			}
		}
	}	
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12672 KB Output is correct
2 Correct 397 ms 30604 KB Output is correct
3 Correct 438 ms 30860 KB Output is correct
4 Correct 439 ms 30840 KB Output is correct
5 Correct 451 ms 30968 KB Output is correct
6 Correct 297 ms 30200 KB Output is correct
7 Correct 433 ms 30584 KB Output is correct
8 Correct 489 ms 30856 KB Output is correct
9 Correct 455 ms 30968 KB Output is correct
10 Correct 290 ms 30200 KB Output is correct
11 Correct 432 ms 30584 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12416 KB Output is correct
2 Correct 2889 ms 154324 KB Output is correct
3 Correct 4003 ms 156116 KB Output is correct
4 Correct 892 ms 88028 KB Output is correct
5 Correct 4564 ms 185048 KB Output is correct
6 Correct 4053 ms 158220 KB Output is correct
7 Correct 1555 ms 57732 KB Output is correct
8 Correct 506 ms 46700 KB Output is correct
9 Correct 1699 ms 62204 KB Output is correct
10 Correct 1568 ms 59128 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12672 KB Output is correct
2 Correct 397 ms 30604 KB Output is correct
3 Correct 438 ms 30860 KB Output is correct
4 Correct 439 ms 30840 KB Output is correct
5 Correct 451 ms 30968 KB Output is correct
6 Correct 297 ms 30200 KB Output is correct
7 Correct 433 ms 30584 KB Output is correct
8 Correct 489 ms 30856 KB Output is correct
9 Correct 455 ms 30968 KB Output is correct
10 Correct 290 ms 30200 KB Output is correct
11 Correct 432 ms 30584 KB Output is correct
12 Correct 10 ms 12416 KB Output is correct
13 Correct 2889 ms 154324 KB Output is correct
14 Correct 4003 ms 156116 KB Output is correct
15 Correct 892 ms 88028 KB Output is correct
16 Correct 4564 ms 185048 KB Output is correct
17 Correct 4053 ms 158220 KB Output is correct
18 Correct 1555 ms 57732 KB Output is correct
19 Correct 506 ms 46700 KB Output is correct
20 Correct 1699 ms 62204 KB Output is correct
21 Correct 1568 ms 59128 KB Output is correct
22 Correct 3781 ms 161400 KB Output is correct
23 Correct 3981 ms 164172 KB Output is correct
24 Correct 5006 ms 163952 KB Output is correct
25 Correct 5014 ms 167928 KB Output is correct
26 Correct 5031 ms 164088 KB Output is correct
27 Correct 6079 ms 187756 KB Output is correct
28 Correct 1158 ms 98524 KB Output is correct
29 Correct 5013 ms 163728 KB Output is correct
30 Correct 5418 ms 163224 KB Output is correct
31 Correct 5538 ms 164004 KB Output is correct
32 Correct 1860 ms 63224 KB Output is correct
33 Correct 555 ms 47056 KB Output is correct
34 Correct 1265 ms 55544 KB Output is correct
35 Correct 1291 ms 55804 KB Output is correct
36 Correct 1543 ms 56184 KB Output is correct
37 Correct 1498 ms 56088 KB Output is correct