oj.uz

Submission #886244

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

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define cln(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define unq(a, n); {vector<int> v; for(int i = 0; i < n; i++) v.pb(a[i]); cln(v); for (int i = 0; i < n; i++) a[i] = lower_bound(all(v), a[i]) - v.begin();}

const ll N = 5e5 + 12, inf = 1e18 + 12;
vector<pii> 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.F != par && !mrk[i.F]) {
			dfs(i.F, u);
			sz[u] += sz[i.F];
		}
}

int find_centroid(int u, int c, int par = -1) {
	for (auto i: g[u])
		if (!mrk[i.F] && i.F != par && sz[i.F] > (c - 1) / 2)
			return find_centroid(i.F, 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.F] && i.F != par)
			fill_cdis(i.F, cent, c + i.S, 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.F])
			decompose(i.F, u);
}

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

ll ask(int u, int v) {
	if (u == -1)
		return inf;
	ll tmp = cdis[u].lower_bound({v, -1})->S;
	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]].pb({b[i], d[i]});
		g[b[i]].pb({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 30 ms 60252 KB Output is correct
2 Correct 1141 ms 71300 KB Output is correct
3 Correct 1747 ms 72036 KB Output is correct
4 Correct 1751 ms 71964 KB Output is correct
5 Correct 2083 ms 77536 KB Output is correct
6 Correct 347 ms 74616 KB Output is correct
7 Correct 1783 ms 76680 KB Output is correct
8 Correct 1772 ms 76720 KB Output is correct
9 Correct 2090 ms 77536 KB Output is correct
10 Correct 343 ms 74308 KB Output is correct
11 Correct 1772 ms 76796 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 8106 ms 411396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 60252 KB Output is correct
2 Correct 1141 ms 71300 KB Output is correct
3 Correct 1747 ms 72036 KB Output is correct
4 Correct 1751 ms 71964 KB Output is correct
5 Correct 2083 ms 77536 KB Output is correct
6 Correct 347 ms 74616 KB Output is correct
7 Correct 1783 ms 76680 KB Output is correct
8 Correct 1772 ms 76720 KB Output is correct
9 Correct 2090 ms 77536 KB Output is correct
10 Correct 343 ms 74308 KB Output is correct
11 Correct 1772 ms 76796 KB Output is correct
12 Correct 12 ms 59996 KB Output is correct
13 Execution timed out 8106 ms 411396 KB Time limit exceeded
14 Halted 0 ms 0 KB -