oj.uz

Submission #411055

# Submission time Handle Problem Language Result Execution time Memory
411055 2021-05-24T08:10:45 Z dynam1c Factories (JOI14_factories) C++17
15 / 100
 8000 ms 258544 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;
vector<vector<int>> a, b;
void Init(int nn, int aa[], int bb[], int d[]) {
	n = nn;
	graph.resize(n);
	ctree.resize(n);
	a.resize(n);
	b.resize(n);
	depth.assign(L, vector<ll>(n));
	subtree.assign(L, vector<ll>(n));
	for (int i = 0; i < n-1; i++) {
		graph[aa[i]].emplace_back(bb[i], d[i]);
		graph[bb[i]].emplace_back(aa[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[]) {
	function<ll(int, int)> calc = [&](int v, int l) {
		if (a[v].empty() or b[v].empty()) return LLONG_MAX;
		for (int ne : ctree[v])
			a[ne].clear(), b[ne].clear();
		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;
	};
	a[croot].clear();
	b[croot].clear();
	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 12 ms 796 KB Output is correct
2 Correct 521 ms 11632 KB Output is correct
3 Correct 693 ms 11524 KB Output is correct
4 Correct 448 ms 11612 KB Output is correct
5 Correct 673 ms 12168 KB Output is correct
6 Correct 611 ms 11412 KB Output is correct
7 Correct 675 ms 11460 KB Output is correct
8 Correct 445 ms 11556 KB Output is correct
9 Correct 681 ms 12152 KB Output is correct
10 Correct 594 ms 11260 KB Output is correct
11 Correct 679 ms 11552 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2850 ms 251424 KB Output is correct
3 Correct 4237 ms 258544 KB Output is correct
4 Execution timed out 8060 ms 244724 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 796 KB Output is correct
2 Correct 521 ms 11632 KB Output is correct
3 Correct 693 ms 11524 KB Output is correct
4 Correct 448 ms 11612 KB Output is correct
5 Correct 673 ms 12168 KB Output is correct
6 Correct 611 ms 11412 KB Output is correct
7 Correct 675 ms 11460 KB Output is correct
8 Correct 445 ms 11556 KB Output is correct
9 Correct 681 ms 12152 KB Output is correct
10 Correct 594 ms 11260 KB Output is correct
11 Correct 679 ms 11552 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 2850 ms 251424 KB Output is correct
14 Correct 4237 ms 258544 KB Output is correct
15 Execution timed out 8060 ms 244724 KB Time limit exceeded
16 Halted 0 ms 0 KB -