oj.uz

Submission #733800

# Submission time Handle Problem Language Result Execution time Memory
733800 2023-05-01T10:30:41 Z PoPularPlusPlus Factories (JOI14_factories) C++17
15 / 100
 8000 ms 192908 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];

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 centroid_decomposition(int node ,int par){
	size_init(node , node);
	node = find_centroid(node , node , siz[node]);
	p[node] = par;
	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++){
		int node = X[i];
		res[node] = 0;
		node = p[node];
		while(node != -1){
			int lca = find(X[i] , node);
			ll distance = cal(X[i],lca) + cal(node,lca);
			if(res[node] == -1 || res[node] > distance){
				res[node] = distance;
				//cout << node << ' ' << X[i] << ' ' << lca << ' ' << distance << '\n';
			}
			node = p[node];
		}
	}
		for(int i = 0; i < b; i++){
			int node = Y[i];
			while(node != -1){
				if(res[node] != -1){
					int lca = find(Y[i],node);
					ll distance = cal(Y[i],lca) + cal(node,lca);
					ans = min(ans , res[node] + distance);
					//cout << node << ' ' << res[node] << ' ' << distance << '\n';
				}
				node = p[node];
			}
		}
		for(int i = 0; i < a; i++){
			int node = X[i];
			while(node != -1){
				if(res[node]==-1)break;
				res[node] = -1;
				node = p[node];
			}
		}
		return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16916 KB Output is correct
2 Correct 1185 ms 35372 KB Output is correct
3 Correct 2623 ms 35544 KB Output is correct
4 Correct 2028 ms 35676 KB Output is correct
5 Correct 2556 ms 35940 KB Output is correct
6 Correct 276 ms 35432 KB Output is correct
7 Correct 2636 ms 35688 KB Output is correct
8 Correct 2633 ms 35472 KB Output is correct
9 Correct 2556 ms 35812 KB Output is correct
10 Correct 351 ms 35400 KB Output is correct
11 Correct 2762 ms 35456 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16752 KB Output is correct
2 Correct 3100 ms 191876 KB Output is correct
3 Execution timed out 8077 ms 192908 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16916 KB Output is correct
2 Correct 1185 ms 35372 KB Output is correct
3 Correct 2623 ms 35544 KB Output is correct
4 Correct 2028 ms 35676 KB Output is correct
5 Correct 2556 ms 35940 KB Output is correct
6 Correct 276 ms 35432 KB Output is correct
7 Correct 2636 ms 35688 KB Output is correct
8 Correct 2633 ms 35472 KB Output is correct
9 Correct 2556 ms 35812 KB Output is correct
10 Correct 351 ms 35400 KB Output is correct
11 Correct 2762 ms 35456 KB Output is correct
12 Correct 12 ms 16752 KB Output is correct
13 Correct 3100 ms 191876 KB Output is correct
14 Execution timed out 8077 ms 192908 KB Time limit exceeded
15 Halted 0 ms 0 KB -