oj.uz

Submission #682761

# Submission time Handle Problem Language Result Execution time Memory
682761 2023-01-17T01:21:36 Z NK_ Factories (JOI14_factories) C++17
100 / 100
 5310 ms 217756 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

#define nl '\n'

using ll = long long;
using E = array<int, 2>;

const int nax = 5e5+5;
vector<E> adj[nax];
bool vis[nax];
vector<ll> dst[nax];
int par[nax], siz[nax];
ll dx[nax];


const ll INFL = ll(1e18) + 10;

// START OF CENTROID DECOMPOSITION
int find_size(int u, int p = -1) {
	if (vis[u]) return 0;
	siz[u] = 1;
	for(auto e : adj[u]) {
		auto [v, w] = e; 
		if (v == p) continue;
		siz[u] += find_size(v, u);
	}
	return siz[u];
}

int find_centroid(int u, int p, int n) {
	for(auto e : adj[u]) {
		auto [v, w] = e;
		if (v == p) continue;
		if (!vis[v] && siz[v] > n / 2) return find_centroid(v, u, n);
	}
	return u;
}

void dfs2(int u, int p = -1) {
	for(auto e : adj[u]) {
		auto [v, w] = e; 
		if (v == p || vis[v]) continue;
		dst[v].push_back(dst[u].back() + w);
		dfs2(v, u);
	}
}

void init_centroid(int u = 0, int p = -1) {
	find_size(u);

	int c = find_centroid(u, -1, siz[u]);
	
	dst[c].push_back(0);
	dfs2(c);
	
	vis[c] = 1;
	par[c] = p;

	for(auto e : adj[c]) {
		auto [v, wv] = e;
		if (vis[v]) continue;
		init_centroid(v, c);
	}

}
// END OF CENTROID DECOMPOSITION


void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N; i++) {
		vis[i] = 0; par[i] = -1;
		dx[i] = INFL;
		adj[i] = {};
		siz[i] = 0;
	}

	for(int i = 0; i < N-1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}

	init_centroid();

	for(int i = 0; i < N; i++) reverse(begin(dst[i]), end(dst[i]));
}

ll Query(int S, int X[], int T, int Y[]) {
	vector<int> alt;
	for(int i = 0; i < S; i++) {
		int u = X[i]; 
		dx[u] = 0; alt.push_back(u);
		int jump = 0;
		while(par[u] != -1) {
			u = par[u];
			alt.push_back(u);
			dx[u] = min(dx[u], dst[X[i]][++jump]);
		}
	}

	ll ans = INFL;
	for(int i = 0; i < T; i++) {
		int u = Y[i];
		int jump = 0;
		while(u != -1) {
			ans = min(ans, dx[u] + dst[Y[i]][jump++]);
			u = par[u];
		}
	}

	sort(begin(alt), end(alt)); alt.erase(unique(begin(alt), end(alt)), end(alt));

	for(auto u : alt) dx[u] = INFL;

	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24148 KB Output is correct
2 Correct 556 ms 32640 KB Output is correct
3 Correct 665 ms 32920 KB Output is correct
4 Correct 693 ms 33300 KB Output is correct
5 Correct 846 ms 33264 KB Output is correct
6 Correct 248 ms 32312 KB Output is correct
7 Correct 664 ms 32904 KB Output is correct
8 Correct 695 ms 32876 KB Output is correct
9 Correct 824 ms 33256 KB Output is correct
10 Correct 273 ms 32396 KB Output is correct
11 Correct 664 ms 32940 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23904 KB Output is correct
2 Correct 2267 ms 130120 KB Output is correct
3 Correct 3284 ms 165652 KB Output is correct
4 Correct 732 ms 79960 KB Output is correct
5 Correct 4221 ms 214228 KB Output is correct
6 Correct 3451 ms 166648 KB Output is correct
7 Correct 1399 ms 54364 KB Output is correct
8 Correct 395 ms 44084 KB Output is correct
9 Correct 1570 ms 62744 KB Output is correct
10 Correct 1368 ms 55648 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24148 KB Output is correct
2 Correct 556 ms 32640 KB Output is correct
3 Correct 665 ms 32920 KB Output is correct
4 Correct 693 ms 33300 KB Output is correct
5 Correct 846 ms 33264 KB Output is correct
6 Correct 248 ms 32312 KB Output is correct
7 Correct 664 ms 32904 KB Output is correct
8 Correct 695 ms 32876 KB Output is correct
9 Correct 824 ms 33256 KB Output is correct
10 Correct 273 ms 32396 KB Output is correct
11 Correct 664 ms 32940 KB Output is correct
12 Correct 15 ms 23904 KB Output is correct
13 Correct 2267 ms 130120 KB Output is correct
14 Correct 3284 ms 165652 KB Output is correct
15 Correct 732 ms 79960 KB Output is correct
16 Correct 4221 ms 214228 KB Output is correct
17 Correct 3451 ms 166648 KB Output is correct
18 Correct 1399 ms 54364 KB Output is correct
19 Correct 395 ms 44084 KB Output is correct
20 Correct 1570 ms 62744 KB Output is correct
21 Correct 1368 ms 55648 KB Output is correct
22 Correct 2780 ms 134388 KB Output is correct
23 Correct 2947 ms 140096 KB Output is correct
24 Correct 4295 ms 174468 KB Output is correct
25 Correct 4345 ms 176232 KB Output is correct
26 Correct 4222 ms 168132 KB Output is correct
27 Correct 5310 ms 217756 KB Output is correct
28 Correct 907 ms 84784 KB Output is correct
29 Correct 4215 ms 167472 KB Output is correct
30 Correct 4135 ms 167124 KB Output is correct
31 Correct 4127 ms 167480 KB Output is correct
32 Correct 1771 ms 68108 KB Output is correct
33 Correct 381 ms 44816 KB Output is correct
34 Correct 1010 ms 50288 KB Output is correct
35 Correct 1042 ms 50564 KB Output is correct
36 Correct 1444 ms 53236 KB Output is correct
37 Correct 1477 ms 53196 KB Output is correct