oj.uz

Submission #734030

# Submission time Handle Problem Language Result Execution time Memory
734030 2023-05-01T14:12:16 Z PoPularPlusPlus Factories (JOI14_factories) C++17
100 / 100
 4564 ms 359036 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;
int n;
vector<pair<int,int>> adj[N];
//int tin[N],tout[N],timer,up[N][L];
//ll dis[N][L];
//int p[N];
bool vis[N];
int siz[N];
ll res[N];

vector<pair<int,ll>> v[N];
/*
void dfs(int node , int par , int di){
	tin[node] = timer++;
	up[node][0] = par;
	dis[node][0] = di;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
		dis[node][i] = dis[node][i-1] + dis[up[node][i-1]][i-1];
	}
	for(auto i : adj[node]){
		if(i.vf != par){
			dfs(i.vf , node , i.vs);
		}
	}
	tout[node] = timer++;
}
 
bool is_lca(int x , int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}
 
int find(int x , int y){
	if(is_lca(x,y))return x;
	if(is_lca(y,x))return y;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i] , y))x = up[x][i];
	}
	return up[x][0];
}

*/

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]);
	//p[node] = par;
	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]));
	}
	//timer = 0;
	//dfs(0,0,0);
	memset(vis,0,sizeof vis);
	centroid_decomposition(0,-1);
	memset(res,-1,sizeof res);
}
/*
ll cal(int x , int y){
	if(x == y)return 0;
	if(is_lca(x,y))swap(x,y);
	ll ans = 0;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i] , y)){
			ans += dis[x][i];
			x = up[x][i];
		}
	}
	ans += dis[x][0];
	return ans;
}
*/
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 20 ms 28760 KB Output is correct
2 Correct 326 ms 42720 KB Output is correct
3 Correct 337 ms 43208 KB Output is correct
4 Correct 345 ms 43184 KB Output is correct
5 Correct 388 ms 43680 KB Output is correct
6 Correct 240 ms 42148 KB Output is correct
7 Correct 338 ms 43288 KB Output is correct
8 Correct 362 ms 43212 KB Output is correct
9 Correct 373 ms 43620 KB Output is correct
10 Correct 250 ms 42208 KB Output is correct
11 Correct 349 ms 43128 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28412 KB Output is correct
2 Correct 2183 ms 189072 KB Output is correct
3 Correct 3230 ms 261580 KB Output is correct
4 Correct 824 ms 104184 KB Output is correct
5 Correct 4387 ms 356268 KB Output is correct
6 Correct 3274 ms 280520 KB Output is correct
7 Correct 962 ms 85508 KB Output is correct
8 Correct 442 ms 62700 KB Output is correct
9 Correct 1120 ms 98040 KB Output is correct
10 Correct 997 ms 86964 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28760 KB Output is correct
2 Correct 326 ms 42720 KB Output is correct
3 Correct 337 ms 43208 KB Output is correct
4 Correct 345 ms 43184 KB Output is correct
5 Correct 388 ms 43680 KB Output is correct
6 Correct 240 ms 42148 KB Output is correct
7 Correct 338 ms 43288 KB Output is correct
8 Correct 362 ms 43212 KB Output is correct
9 Correct 373 ms 43620 KB Output is correct
10 Correct 250 ms 42208 KB Output is correct
11 Correct 349 ms 43128 KB Output is correct
12 Correct 18 ms 28412 KB Output is correct
13 Correct 2183 ms 189072 KB Output is correct
14 Correct 3230 ms 261580 KB Output is correct
15 Correct 824 ms 104184 KB Output is correct
16 Correct 4387 ms 356268 KB Output is correct
17 Correct 3274 ms 280520 KB Output is correct
18 Correct 962 ms 85508 KB Output is correct
19 Correct 442 ms 62700 KB Output is correct
20 Correct 1120 ms 98040 KB Output is correct
21 Correct 997 ms 86964 KB Output is correct
22 Correct 2570 ms 212720 KB Output is correct
23 Correct 2647 ms 217764 KB Output is correct
24 Correct 3815 ms 286516 KB Output is correct
25 Correct 3952 ms 290924 KB Output is correct
26 Correct 3724 ms 287620 KB Output is correct
27 Correct 4564 ms 359036 KB Output is correct
28 Correct 1140 ms 114616 KB Output is correct
29 Correct 3679 ms 287028 KB Output is correct
30 Correct 3634 ms 286540 KB Output is correct
31 Correct 3729 ms 286952 KB Output is correct
32 Correct 1296 ms 98664 KB Output is correct
33 Correct 517 ms 63124 KB Output is correct
34 Correct 841 ms 77532 KB Output is correct
35 Correct 898 ms 78376 KB Output is correct
36 Correct 1151 ms 83900 KB Output is correct
37 Correct 1125 ms 84120 KB Output is correct