oj.uz

Submission #734032

# Submission time Handle Problem Language Result Execution time Memory
734032 2023-05-01T14:14:47 Z PoPularPlusPlus Factories (JOI14_factories) C++17
100 / 100
 4549 ms 337520 KB 
#include "factories.h"
#include <bits/stdc++.h>
 
using namespace std; 
 
#define ll long long
#define pb(e) push_back(e)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
 
const int N = 500002,L=20;
vector<pair<int,int>> adj[N];
bool vis[N];
int siz[N],n;
ll res[N];
vector<pair<int,ll>> v[N];

void size_init(int node , int par){
	siz[node] = 1;
	for(auto i : adj[node]){
		if(i.vf != par && !vis[i.vf]){
			size_init(i.vf,node);
			siz[node] += siz[i.vf];
		}
	}
}

int find_centroid(int node , int par , int total){
	for(auto i :  adj[node]){
		if(!vis[i.vf] && i.vf != par && siz[i.vf] >= total/2)return find_centroid(i.vf , node , total);
	}
	return node;
}

void pre_dfs(int node , int par , int root , ll distance){
	v[node].pb(mp(root,distance));
	for(auto i : adj[node]){
		if(!vis[i.vf] && i.vf != par){
			pre_dfs(i.vf , node , root , distance + i.vs);
		}
	}
}

void centroid_decomposition(int node ,int par){
	size_init(node , node);
	node = find_centroid(node , node , siz[node]);
	pre_dfs(node , node , node , 0);
	vis[node] = 1;
	for(auto i : adj[node]){
		if(!vis[i.vf]){
			centroid_decomposition(i.vf , node);
		}
	}
}
 
void Init(int nn, int A[], int B[], int D[]) {
	n = nn;
	for(int i = 0; i < n-1; i++){
		adj[A[i]].pb(mp(B[i],D[i]));
		adj[B[i]].pb(mp(A[i],D[i]));
	}
	memset(vis,0,sizeof vis);
	centroid_decomposition(0,-1);
	memset(res,-1,sizeof res);
}

long long Query(int a, int X[], int b, int Y[]) {
	ll ans = 1e18;
	for(int i = 0; i < a; i++){
		for(auto it : v[X[i]]){
			if(res[it.vf] == -1)res[it.vf] = it.vs;
			else res[it.vf] = min(res[it.vf] , it.vs);
		}
	}
		for(int i = 0; i < b; i++){
			for(auto it : v[Y[i]]){
				if(res[it.vf] != -1){
					ans = min(ans , res[it.vf] + it.vs);
				}
			}
		}
		for(int i = 0; i < a; i++){
			for(auto it : v[X[i]]){
				res[it.vf] = -1;
			}
		}
		return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28500 KB Output is correct
2 Correct 307 ms 37248 KB Output is correct
3 Correct 371 ms 37644 KB Output is correct
4 Correct 319 ms 37708 KB Output is correct
5 Correct 368 ms 38052 KB Output is correct
6 Correct 204 ms 36700 KB Output is correct
7 Correct 328 ms 37628 KB Output is correct
8 Correct 326 ms 37824 KB Output is correct
9 Correct 368 ms 38112 KB Output is correct
10 Correct 194 ms 36700 KB Output is correct
11 Correct 322 ms 37692 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28408 KB Output is correct
2 Correct 2185 ms 188884 KB Output is correct
3 Correct 3277 ms 261288 KB Output is correct
4 Correct 850 ms 85856 KB Output is correct
5 Correct 4330 ms 337520 KB Output is correct
6 Correct 3325 ms 261672 KB Output is correct
7 Correct 964 ms 71668 KB Output is correct
8 Correct 394 ms 48700 KB Output is correct
9 Correct 1202 ms 84068 KB Output is correct
10 Correct 1082 ms 72884 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28500 KB Output is correct
2 Correct 307 ms 37248 KB Output is correct
3 Correct 371 ms 37644 KB Output is correct
4 Correct 319 ms 37708 KB Output is correct
5 Correct 368 ms 38052 KB Output is correct
6 Correct 204 ms 36700 KB Output is correct
7 Correct 328 ms 37628 KB Output is correct
8 Correct 326 ms 37824 KB Output is correct
9 Correct 368 ms 38112 KB Output is correct
10 Correct 194 ms 36700 KB Output is correct
11 Correct 322 ms 37692 KB Output is correct
12 Correct 15 ms 28408 KB Output is correct
13 Correct 2185 ms 188884 KB Output is correct
14 Correct 3277 ms 261288 KB Output is correct
15 Correct 850 ms 85856 KB Output is correct
16 Correct 4330 ms 337520 KB Output is correct
17 Correct 3325 ms 261672 KB Output is correct
18 Correct 964 ms 71668 KB Output is correct
19 Correct 394 ms 48700 KB Output is correct
20 Correct 1202 ms 84068 KB Output is correct
21 Correct 1082 ms 72884 KB Output is correct
22 Correct 2672 ms 188484 KB Output is correct
23 Correct 2721 ms 193124 KB Output is correct
24 Correct 4100 ms 262196 KB Output is correct
25 Correct 3996 ms 266192 KB Output is correct
26 Correct 3815 ms 263372 KB Output is correct
27 Correct 4549 ms 334324 KB Output is correct
28 Correct 1040 ms 90024 KB Output is correct
29 Correct 3976 ms 262612 KB Output is correct
30 Correct 3687 ms 262196 KB Output is correct
31 Correct 3585 ms 262728 KB Output is correct
32 Correct 1221 ms 84524 KB Output is correct
33 Correct 415 ms 49072 KB Output is correct
34 Correct 787 ms 63960 KB Output is correct
35 Correct 799 ms 64680 KB Output is correct
36 Correct 985 ms 70196 KB Output is correct
37 Correct 964 ms 70320 KB Output is correct