oj.uz

Submission #886253

# Submission time Handle Problem Language Result Execution time Memory
886253 2023-12-11T15:56:43 Z javotaz Factories (JOI14_factories) C++17
15 / 100
 8000 ms 411256 KB 
// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 5e5 + 12, inf = 1e18 + 12;
vector<pair<int, int>> g[N];
int sz[N], cpar[N], q, n;
ll val[N];
set<pair<int, ll>> cdis[N];
bool mrk[N];

void dfs(int u, int par = -1) {
	sz[u] = 1;
	for (auto i: g[u])
		if (i.first != par && !mrk[i.first]) {
			dfs(i.first, u);
			sz[u] += sz[i.first];
		}
}

int find_centroid(int u, int c, int par = -1) {
	for (auto i: g[u])
		if (!mrk[i.first] && i.first != par && sz[i.first] > (c - 1) / 2)
			return find_centroid(i.first, c, u);
	return u;
}

void fill_cdis(int u, int cent, ll c = 0, int par = -1) {
	cdis[cent].insert({u, c});
	for (auto i: g[u])
		if (!mrk[i.first] && i.first != par)
			fill_cdis(i.first, cent, c + i.second, u);
}

void decompose(int u, int par = -1) {
	dfs(u);
	u = find_centroid(u, sz[u]);
	fill_cdis(u, u);
	cpar[u] = par;
	mrk[u] = true;
	for (auto i: g[u])
		if (!mrk[i.first])
			decompose(i.first, u);
}

void add(int u, int v) {
	if (u == -1)
		return;
	val[u] = min(val[u], cdis[u].lower_bound({v, -1})->second);
	add(cpar[u], v);
}

ll ask(int u, int v) {
	if (u == -1)
		return inf;
	ll tmp = cdis[u].lower_bound({v, -1})->second;
	return min(ask(cpar[u], v), tmp + val[u]);
}

void rem(int u) {
	val[u] = inf;
	if (cpar[u] != -1)
		rem(cpar[u]);
}

void Init(int c, int a[], int b[], int d[]) {
	n = c;
	for (int i = 0; i < n - 1; i++) {
		g[a[i]].push_back({b[i], d[i]});
		g[b[i]].push_back({a[i], d[i]});
	}
	decompose(0);
	fill(val, val + n, inf);
}

ll Query(int s, int x[], int t, int y[]) {
	for (int i = 0; i < s; i++)
		add(x[i], x[i]);
	ll res = inf;
	for (int i = 0; i < t; i++)
		res = min(res, ask(y[i], y[i]));
	for (int i = 0; i < s; i++)
		rem(x[i]);
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 59988 KB Output is correct
2 Correct 1141 ms 66388 KB Output is correct
3 Correct 1782 ms 67412 KB Output is correct
4 Correct 1784 ms 67348 KB Output is correct
5 Correct 2103 ms 68112 KB Output is correct
6 Correct 345 ms 64852 KB Output is correct
7 Correct 1814 ms 67344 KB Output is correct
8 Correct 1776 ms 67264 KB Output is correct
9 Correct 2185 ms 68180 KB Output is correct
10 Correct 348 ms 64776 KB Output is correct
11 Correct 1770 ms 67388 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59996 KB Output is correct
2 Execution timed out 8096 ms 411256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 59988 KB Output is correct
2 Correct 1141 ms 66388 KB Output is correct
3 Correct 1782 ms 67412 KB Output is correct
4 Correct 1784 ms 67348 KB Output is correct
5 Correct 2103 ms 68112 KB Output is correct
6 Correct 345 ms 64852 KB Output is correct
7 Correct 1814 ms 67344 KB Output is correct
8 Correct 1776 ms 67264 KB Output is correct
9 Correct 2185 ms 68180 KB Output is correct
10 Correct 348 ms 64776 KB Output is correct
11 Correct 1770 ms 67388 KB Output is correct
12 Correct 12 ms 59996 KB Output is correct
13 Execution timed out 8096 ms 411256 KB Time limit exceeded
14 Halted 0 ms 0 KB -