oj.uz

Submission #886269

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

#pragma  GCC optimize ("O2,unroll-loops")
#pragma  GCC optimize ("Ofast")
#pragma  gcc optimize("Ofast")
#pragma  optimize(Ofast)

typedef long long ll;

const ll N = 5e5 + 12, inf = 1e18 + 12, M = 22;
vector<pair<int, int>> g[N];
int sz[N], cpar[N], q, n, h[N];
ll val[N], cdis[N][M];
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 lay, ll c = 0, int par = -1) {
	cdis[u][lay] = c;
	for (auto i: g[u])
		if (!mrk[i.first] && i.first != par)
			fill_cdis(i.first, lay, c + i.second, u);
}

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

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

ll ask(int u, int v, int lay) {
	if (u == -1)
		return inf;
	return min(ask(cpar[u], v, lay - 1), cdis[v][lay] + 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], h[x[i]]);
	ll res = inf;
	for (int i = 0; i < t; i++)
		res = min(res, ask(y[i], y[i], h[y[i]]));
	for (int i = 0; i < s; i++)
		rem(x[i]);
	return res;
}

Compilation message

factories.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    8 | #pragma  gcc optimize("Ofast")
      | 
factories.cpp:9: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    9 | #pragma  optimize(Ofast)
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39260 KB Output is correct
2 Correct 222 ms 43748 KB Output is correct
3 Correct 231 ms 43740 KB Output is correct
4 Correct 226 ms 43600 KB Output is correct
5 Correct 240 ms 43816 KB Output is correct
6 Correct 161 ms 43744 KB Output is correct
7 Correct 223 ms 43504 KB Output is correct
8 Correct 254 ms 43764 KB Output is correct
9 Correct 250 ms 43820 KB Output is correct
10 Correct 152 ms 43752 KB Output is correct
11 Correct 238 ms 43708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 1071 ms 150732 KB Output is correct
3 Correct 1727 ms 151568 KB Output is correct
4 Correct 443 ms 151224 KB Output is correct
5 Correct 2428 ms 161988 KB Output is correct
6 Correct 1754 ms 151832 KB Output is correct
7 Correct 527 ms 64336 KB Output is correct
8 Correct 228 ms 64584 KB Output is correct
9 Correct 618 ms 66024 KB Output is correct
10 Correct 518 ms 64992 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39260 KB Output is correct
2 Correct 222 ms 43748 KB Output is correct
3 Correct 231 ms 43740 KB Output is correct
4 Correct 226 ms 43600 KB Output is correct
5 Correct 240 ms 43816 KB Output is correct
6 Correct 161 ms 43744 KB Output is correct
7 Correct 223 ms 43504 KB Output is correct
8 Correct 254 ms 43764 KB Output is correct
9 Correct 250 ms 43820 KB Output is correct
10 Correct 152 ms 43752 KB Output is correct
11 Correct 238 ms 43708 KB Output is correct
12 Correct 6 ms 39256 KB Output is correct
13 Correct 1071 ms 150732 KB Output is correct
14 Correct 1727 ms 151568 KB Output is correct
15 Correct 443 ms 151224 KB Output is correct
16 Correct 2428 ms 161988 KB Output is correct
17 Correct 1754 ms 151832 KB Output is correct
18 Correct 527 ms 64336 KB Output is correct
19 Correct 228 ms 64584 KB Output is correct
20 Correct 618 ms 66024 KB Output is correct
21 Correct 518 ms 64992 KB Output is correct
22 Correct 1239 ms 149712 KB Output is correct
23 Correct 1328 ms 150724 KB Output is correct
24 Correct 1943 ms 150464 KB Output is correct
25 Correct 2091 ms 152440 KB Output is correct
26 Correct 2110 ms 150940 KB Output is correct
27 Correct 2631 ms 158900 KB Output is correct
28 Correct 576 ms 176028 KB Output is correct
29 Correct 1989 ms 174728 KB Output is correct
30 Correct 2051 ms 174464 KB Output is correct
31 Correct 1981 ms 174916 KB Output is correct
32 Correct 653 ms 80316 KB Output is correct
33 Correct 226 ms 78900 KB Output is correct
34 Correct 418 ms 77292 KB Output is correct
35 Correct 399 ms 77300 KB Output is correct
36 Correct 497 ms 77640 KB Output is correct
37 Correct 523 ms 77500 KB Output is correct