oj.uz

Submission #411062

# Submission time Handle Problem Language Result Execution time Memory
411062 2021-05-24T08:36:21 Z dynam1c Factories (JOI14_factories) C++17
33 / 100
 8000 ms 313548 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;
vector<bool> vis;
vector<int> sz;
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];
}
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;
}
void Init(int nn, int aa[], int bb[], int d[]) {
	n = nn;
	graph.resize(n);
	ctree.resize(n);
	a.resize(n);
	b.resize(n);
	vis.resize(n);
	sz.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]);
	}
	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 15 ms 972 KB Output is correct
2 Correct 645 ms 11352 KB Output is correct
3 Correct 908 ms 11460 KB Output is correct
4 Correct 550 ms 11448 KB Output is correct
5 Correct 1029 ms 11992 KB Output is correct
6 Correct 336 ms 11140 KB Output is correct
7 Correct 897 ms 11332 KB Output is correct
8 Correct 590 ms 11476 KB Output is correct
9 Correct 1006 ms 11924 KB Output is correct
10 Correct 297 ms 11328 KB Output is correct
11 Correct 847 ms 11280 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 2710 ms 251708 KB Output is correct
3 Correct 4182 ms 256800 KB Output is correct
4 Correct 1387 ms 264848 KB Output is correct
5 Correct 4828 ms 299292 KB Output is correct
6 Correct 4088 ms 257864 KB Output is correct
7 Correct 2224 ms 60700 KB Output is correct
8 Correct 787 ms 64672 KB Output is correct
9 Correct 1997 ms 66932 KB Output is correct
10 Correct 1843 ms 61696 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 972 KB Output is correct
2 Correct 645 ms 11352 KB Output is correct
3 Correct 908 ms 11460 KB Output is correct
4 Correct 550 ms 11448 KB Output is correct
5 Correct 1029 ms 11992 KB Output is correct
6 Correct 336 ms 11140 KB Output is correct
7 Correct 897 ms 11332 KB Output is correct
8 Correct 590 ms 11476 KB Output is correct
9 Correct 1006 ms 11924 KB Output is correct
10 Correct 297 ms 11328 KB Output is correct
11 Correct 847 ms 11280 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 2710 ms 251708 KB Output is correct
14 Correct 4182 ms 256800 KB Output is correct
15 Correct 1387 ms 264848 KB Output is correct
16 Correct 4828 ms 299292 KB Output is correct
17 Correct 4088 ms 257864 KB Output is correct
18 Correct 2224 ms 60700 KB Output is correct
19 Correct 787 ms 64672 KB Output is correct
20 Correct 1997 ms 66932 KB Output is correct
21 Correct 1843 ms 61696 KB Output is correct
22 Correct 4910 ms 272384 KB Output is correct
23 Correct 3237 ms 261340 KB Output is correct
24 Correct 7960 ms 281236 KB Output is correct
25 Correct 7687 ms 283844 KB Output is correct
26 Correct 7951 ms 263284 KB Output is correct
27 Execution timed out 8023 ms 313548 KB Time limit exceeded
28 Halted 0 ms 0 KB -