oj.uz

Submission #792065

# Submission time Handle Problem Language Result Execution time Memory
792065 2023-07-24T14:40:53 Z Blagoj Factories (JOI14_factories) C++17
100 / 100
 3355 ms 178820 KB 
#include <bits/stdc++.h>
#include "factories.h"

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define ll long long

const ll MXN = 500005, INF = 1e18;

bool done[MXN];
int sz[MXN], cen[MXN], temp[MXN];
ll dist[MXN][20], ans[MXN];

vector<pair<int, ll>> g[MXN];

int getSize(int cur, int par = -1) {
	sz[cur] = 1;
	for (auto [next, cost] : g[cur]) {
		if (next != par && !done[next]) sz[cur] += getSize(next, cur);
	}
	return sz[cur];
}

int getCentroid(int cur, int des, int par = -1) {
	for (auto [next, cost] : g[cur]) {
		if (next != par && !done[next] && sz[next] > des / 2) return getCentroid(next, des, cur);
	}
	return cur;
}

void solve(int cur, int par, int top, ll dis) {
	dist[cur][temp[cur]++] = dis;
	for (auto [next, cost] : g[cur]) {
		if (next != par && !done[next]) {
			cen[next] = top;
			solve(next, cur, top, dis + cost);
		}
	}
}

void decomp(int cur) {
	cur = getCentroid(cur, getSize(cur));
	done[cur] = 1;
	solve(cur, cur, cur, 0);
	for (auto [next, cost] : g[cur]) {
		if (!done[next]) decomp(next);
	}
}

void update(int cur, int t = 1) {
	for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
		if (t) ans[Cur] = min(ans[Cur], dist[cur][ind]);
		else ans[Cur] = INF;
	}
} 

ll query(int cur) {
	ll mn = INF;
	for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
		mn = min(mn, ans[Cur] + dist[cur][ind]);
	}
	return mn;
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N; i++) {
		ans[i] = INF;
		cen[i] = -1;
		for (int j = 0; j < 20; j++) dist[i][j] = INF;
		if (i == N - 1) break;
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	decomp(0);
}

ll Query(int S, int X[], int T, int Y[]) { 
	for (int i = 0; i < S; i++) update(X[i]);
	ll mn = INF;
	for (int i = 0; i < T; i++) mn = min(mn, query(Y[i]));
	for (int i = 0; i < S; i++) update(X[i], 0);
	return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12628 KB Output is correct
2 Correct 248 ms 30856 KB Output is correct
3 Correct 255 ms 30684 KB Output is correct
4 Correct 237 ms 30664 KB Output is correct
5 Correct 240 ms 30836 KB Output is correct
6 Correct 176 ms 30704 KB Output is correct
7 Correct 226 ms 30832 KB Output is correct
8 Correct 238 ms 30824 KB Output is correct
9 Correct 291 ms 30900 KB Output is correct
10 Correct 155 ms 30668 KB Output is correct
11 Correct 224 ms 30700 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 1300 ms 157692 KB Output is correct
3 Correct 2151 ms 158032 KB Output is correct
4 Correct 453 ms 154924 KB Output is correct
5 Correct 2899 ms 172016 KB Output is correct
6 Correct 2221 ms 160584 KB Output is correct
7 Correct 533 ms 59616 KB Output is correct
8 Correct 253 ms 59956 KB Output is correct
9 Correct 639 ms 62380 KB Output is correct
10 Correct 593 ms 61076 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12628 KB Output is correct
2 Correct 248 ms 30856 KB Output is correct
3 Correct 255 ms 30684 KB Output is correct
4 Correct 237 ms 30664 KB Output is correct
5 Correct 240 ms 30836 KB Output is correct
6 Correct 176 ms 30704 KB Output is correct
7 Correct 226 ms 30832 KB Output is correct
8 Correct 238 ms 30824 KB Output is correct
9 Correct 291 ms 30900 KB Output is correct
10 Correct 155 ms 30668 KB Output is correct
11 Correct 224 ms 30700 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 1300 ms 157692 KB Output is correct
14 Correct 2151 ms 158032 KB Output is correct
15 Correct 453 ms 154924 KB Output is correct
16 Correct 2899 ms 172016 KB Output is correct
17 Correct 2221 ms 160584 KB Output is correct
18 Correct 533 ms 59616 KB Output is correct
19 Correct 253 ms 59956 KB Output is correct
20 Correct 639 ms 62380 KB Output is correct
21 Correct 593 ms 61076 KB Output is correct
22 Correct 1437 ms 164944 KB Output is correct
23 Correct 1520 ms 167592 KB Output is correct
24 Correct 2574 ms 166884 KB Output is correct
25 Correct 2710 ms 170428 KB Output is correct
26 Correct 2857 ms 166748 KB Output is correct
27 Correct 3355 ms 178820 KB Output is correct
28 Correct 604 ms 165480 KB Output is correct
29 Correct 2738 ms 166608 KB Output is correct
30 Correct 2642 ms 166360 KB Output is correct
31 Correct 2723 ms 166684 KB Output is correct
32 Correct 772 ms 62984 KB Output is correct
33 Correct 289 ms 60308 KB Output is correct
34 Correct 392 ms 57556 KB Output is correct
35 Correct 464 ms 57568 KB Output is correct
36 Correct 605 ms 58052 KB Output is correct
37 Correct 537 ms 58044 KB Output is correct