oj.uz

Submission #411054

# Submission time Handle Problem Language Result Execution time Memory
411054 2021-05-24T08:06:25 Z dynam1c Factories (JOI14_factories) C++17
15 / 100
 8000 ms 249988 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(x) x.begin(), x.end()

vector<vector<pair<int, ll>>> graph;
vector<vector<int>> ctree;
int croot;
vector<vector<ll>> depth, subtree; // [level][v]
constexpr int L = 20;
int n;
void Init(int nn, int a[], int b[], int d[]) {
	n = nn;
	graph.resize(n);
	ctree.resize(n);
	depth.assign(L, vector<ll>(n));
	subtree.assign(L, vector<ll>(n));
	for (int i = 0; i < n-1; i++) {
		graph[a[i]].emplace_back(b[i], d[i]);
		graph[b[i]].emplace_back(a[i], d[i]);
	}
	vector<bool> vis(n);
	vector<int> sz(n);
	function<int(int, int, int, int)> calc = [&](int v, int p, int l, int c) {
		if (v == p and l >= 0)
			depth[l][v] = 0;
		if (l > 0)
			subtree[l-1][v] = c;
		sz[v] = 1;
		for (auto [ne, w] : graph[v])
			if (!vis[ne] and ne != p) {
				if (l >= 0)
					depth[l][ne] = depth[l][v]+w;
				sz[v] += calc(ne, v, l, c);
			}
		return sz[v];
	};
	function<int(int, int)> centroid = [&](int v, int l) {
		int k = calc(v, v, -1, 0), c = v;
		bool cont = true;
		while (cont) {
			cont = false;
			for (auto [ne, w] : graph[c]) if (!vis[ne] and sz[ne] < sz[c] and 2*sz[ne] > k)
				cont = true, c = ne;
		}
		calc(c, c, l, c);
		vis[c] = true;
		for (auto [ne, w] : graph[c]) {
			if (!vis[ne])
				ctree[c].push_back(centroid(ne, l+1));
		}
		return c;
	};
	croot = centroid(0, 0);
}

long long Query(int s, int x[], int t, int y[]) {
	vector<vector<int>> a(n), b(n);
	function<ll(int, int)> calc = [&](int v, int l) {
		if (a[v].empty() or b[v].empty()) return LLONG_MAX;
		/*cout << v << endl;
		for (int e : a[v])
			cout << " " << e;
		cout << endl;
		for (int e : b[v])
			cout << " " << e;
		cout << endl;*/
		ll ax = LLONG_MAX, bx = LLONG_MAX;
		for (int e : a[v]) {
			ax = min(ax, depth[l][e]);
			if (e != v)
				a[subtree[l][e]].push_back(e);
		}
		for (int e : b[v]) {
			bx = min(bx, depth[l][e]);
			if (e != v)
				b[subtree[l][e]].push_back(e);
		}
		ll res = ax+bx;
		for (int ne : ctree[v])
			res = min(res, calc(ne, l+1));
		return res;
	};
	for (int i = 0; i < s; i++)
		a[croot].push_back(x[i]);
	for (int i = 0; i < t; i++)
		b[croot].push_back(y[i]);
	return calc(croot, 0);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 864 KB Output is correct
2 Correct 1004 ms 11336 KB Output is correct
3 Correct 1327 ms 11076 KB Output is correct
4 Correct 736 ms 11512 KB Output is correct
5 Correct 1304 ms 12100 KB Output is correct
6 Correct 783 ms 11224 KB Output is correct
7 Correct 1289 ms 11288 KB Output is correct
8 Correct 743 ms 11464 KB Output is correct
9 Correct 1290 ms 12004 KB Output is correct
10 Correct 796 ms 11376 KB Output is correct
11 Correct 1283 ms 11288 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 588 KB Output is correct
2 Execution timed out 8082 ms 249988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 864 KB Output is correct
2 Correct 1004 ms 11336 KB Output is correct
3 Correct 1327 ms 11076 KB Output is correct
4 Correct 736 ms 11512 KB Output is correct
5 Correct 1304 ms 12100 KB Output is correct
6 Correct 783 ms 11224 KB Output is correct
7 Correct 1289 ms 11288 KB Output is correct
8 Correct 743 ms 11464 KB Output is correct
9 Correct 1290 ms 12004 KB Output is correct
10 Correct 796 ms 11376 KB Output is correct
11 Correct 1283 ms 11288 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Execution timed out 8082 ms 249988 KB Time limit exceeded
14 Halted 0 ms 0 KB -