oj.uz

Submission #411060

# Submission time Handle Problem Language Result Execution time Memory
411060 2021-05-24T08:32:30 Z dynam1c Factories (JOI14_factories) C++17
33 / 100
 8000 ms 322116 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);
}

ll qq(int v, int l) {
	if (a[v].empty() or b[v].empty()) {
		a[v].clear(), b[v].clear();
		return LLONG_MAX;
	}
	ll ax = LLONG_MAX, bx = LLONG_MAX;
	vector<int> nxt;
	for (int e : a[v]) {
		ax = min(ax, depth[l][e]);
		if (e != v) 
			a[subtree[l][e]].push_back(e), nxt.push_back(subtree[l][e]);
	}
	for (int e : b[v]) {
		bx = min(bx, depth[l][e]);
		if (e != v)
			b[subtree[l][e]].push_back(e), nxt.push_back(subtree[l][e]);
	}
	/*cout << v << endl;
	for (int e : a[v])
		cout << " " << e;
	cout << endl;
	for (int e : b[v])
		cout << " " << e;
	cout << endl;*/
	ll res = ax+bx;
	for (int ne : nxt)
		res = min(res, qq(ne, l+1));
	a[v].clear(), b[v].clear();
	return res;
}

long long Query(int s, int x[], int t, int y[]) {
	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 qq(croot, 0);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 844 KB Output is correct
2 Correct 674 ms 11224 KB Output is correct
3 Correct 886 ms 11164 KB Output is correct
4 Correct 564 ms 11380 KB Output is correct
5 Correct 980 ms 11816 KB Output is correct
6 Correct 322 ms 10948 KB Output is correct
7 Correct 867 ms 11064 KB Output is correct
8 Correct 601 ms 11464 KB Output is correct
9 Correct 987 ms 11972 KB Output is correct
10 Correct 304 ms 10948 KB Output is correct
11 Correct 861 ms 11084 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2989 ms 251392 KB Output is correct
3 Correct 4324 ms 258240 KB Output is correct
4 Correct 1386 ms 262756 KB Output is correct
5 Correct 5115 ms 312676 KB Output is correct
6 Correct 4210 ms 259264 KB Output is correct
7 Correct 2077 ms 65072 KB Output is correct
8 Correct 719 ms 68724 KB Output is correct
9 Correct 1876 ms 72772 KB Output is correct
10 Correct 1857 ms 65980 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 844 KB Output is correct
2 Correct 674 ms 11224 KB Output is correct
3 Correct 886 ms 11164 KB Output is correct
4 Correct 564 ms 11380 KB Output is correct
5 Correct 980 ms 11816 KB Output is correct
6 Correct 322 ms 10948 KB Output is correct
7 Correct 867 ms 11064 KB Output is correct
8 Correct 601 ms 11464 KB Output is correct
9 Correct 987 ms 11972 KB Output is correct
10 Correct 304 ms 10948 KB Output is correct
11 Correct 861 ms 11084 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 2989 ms 251392 KB Output is correct
14 Correct 4324 ms 258240 KB Output is correct
15 Correct 1386 ms 262756 KB Output is correct
16 Correct 5115 ms 312676 KB Output is correct
17 Correct 4210 ms 259264 KB Output is correct
18 Correct 2077 ms 65072 KB Output is correct
19 Correct 719 ms 68724 KB Output is correct
20 Correct 1876 ms 72772 KB Output is correct
21 Correct 1857 ms 65980 KB Output is correct
22 Correct 5221 ms 270600 KB Output is correct
23 Correct 3440 ms 259400 KB Output is correct
24 Correct 7930 ms 280812 KB Output is correct
25 Correct 7437 ms 283744 KB Output is correct
26 Correct 7960 ms 263140 KB Output is correct
27 Execution timed out 8064 ms 322116 KB Time limit exceeded
28 Halted 0 ms 0 KB -