oj.uz

Submission #886257

# Submission time Handle Problem Language Result Execution time Memory
886257 2023-12-11T16:07:17 Z javotaz Factories (JOI14_factories) C++17
33 / 100
 8000 ms 524260 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;
vector<pair<int, int>> g[N];
int sz[N], cpar[N], q, n;
ll val[N];
unordered_map<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][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][v]);
	add(cpar[u], v);
}

ll ask(int u, int v) {
	if (u == -1)
		return inf;
	ll tmp = cdis[u][v];
	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;
}

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 22 ms 62660 KB Output is correct
2 Correct 431 ms 68076 KB Output is correct
3 Correct 562 ms 68896 KB Output is correct
4 Correct 542 ms 68688 KB Output is correct
5 Correct 634 ms 69136 KB Output is correct
6 Correct 194 ms 67188 KB Output is correct
7 Correct 544 ms 68664 KB Output is correct
8 Correct 569 ms 68788 KB Output is correct
9 Correct 668 ms 69460 KB Output is correct
10 Correct 203 ms 67152 KB Output is correct
11 Correct 549 ms 68880 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 62044 KB Output is correct
2 Correct 3558 ms 352364 KB Output is correct
3 Correct 5168 ms 465556 KB Output is correct
4 Correct 877 ms 182396 KB Output is correct
5 Correct 6355 ms 524260 KB Output is correct
6 Correct 5521 ms 465568 KB Output is correct
7 Correct 3727 ms 138948 KB Output is correct
8 Correct 451 ms 89780 KB Output is correct
9 Correct 4436 ms 147292 KB Output is correct
10 Correct 3648 ms 139308 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62660 KB Output is correct
2 Correct 431 ms 68076 KB Output is correct
3 Correct 562 ms 68896 KB Output is correct
4 Correct 542 ms 68688 KB Output is correct
5 Correct 634 ms 69136 KB Output is correct
6 Correct 194 ms 67188 KB Output is correct
7 Correct 544 ms 68664 KB Output is correct
8 Correct 569 ms 68788 KB Output is correct
9 Correct 668 ms 69460 KB Output is correct
10 Correct 203 ms 67152 KB Output is correct
11 Correct 549 ms 68880 KB Output is correct
12 Correct 13 ms 62044 KB Output is correct
13 Correct 3558 ms 352364 KB Output is correct
14 Correct 5168 ms 465556 KB Output is correct
15 Correct 877 ms 182396 KB Output is correct
16 Correct 6355 ms 524260 KB Output is correct
17 Correct 5521 ms 465568 KB Output is correct
18 Correct 3727 ms 138948 KB Output is correct
19 Correct 451 ms 89780 KB Output is correct
20 Correct 4436 ms 147292 KB Output is correct
21 Correct 3648 ms 139308 KB Output is correct
22 Correct 4891 ms 347464 KB Output is correct
23 Correct 5048 ms 357704 KB Output is correct
24 Correct 7756 ms 464576 KB Output is correct
25 Correct 7925 ms 465848 KB Output is correct
26 Correct 7876 ms 464696 KB Output is correct
27 Execution timed out 8053 ms 521868 KB Time limit exceeded
28 Halted 0 ms 0 KB -