oj.uz

Submission #359291

# Submission time Handle Problem Language Result Execution time Memory
359291 2021-01-26T16:02:46 Z pure_mem Factories (JOI14_factories) C++14
100 / 100
 7708 ms 199508 KB 
#include "factories.h"
#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

const int N = 5e5 + 2;
const ll INF = 1e18;

int lg[N * 4];
int n, sz[N], mx[N], block[N], cent_pr[N], depth[N], ord[21][N * 4], timer, tin[N];
ll dp[N], mcost[N];
int last_used[N], Q;
vector< pair< int, int > > g[N];

void dfs_sz(int v, int pr){
	sz[v] = 1, mx[v] = 0;
	for(pair<int, int> to: g[v]){
		if(to.X == pr || block[to.X])
			continue;
		dfs_sz(to.X, v), sz[v] += sz[to.X];
		mx[v] = (sz[mx[v]] < sz[to.X] ? to.X: mx[v]);
	}
}

int get_cent(int v){
	int u = v;
	while(sz[mx[u]] * 2 > sz[v])
		u = mx[u];
	return u;
}

void cent(int v, int pr){
	dfs_sz(v, v), v = get_cent(v);
	cent_pr[v] = pr, block[v] = 1;
	for(pair<int, int> to: g[v]){
		if(!block[to.X])
			cent(to.X, v);
	}
}

void dfs_prep(int v, int pr){
	tin[v] = ++timer, ord[0][timer] = v;
	for(pair<int, int> to: g[v]){
		if(to.X == pr)
			continue;
		dp[to.X] = dp[v] + to.Y, depth[to.X] = depth[v] + 1;
		dfs_prep(to.X, v);
		ord[0][++timer] = v;
	}	
}

ll calc(int x, int y){
	if(tin[x] > tin[y])
		swap(x, y);
	int mid = (tin[y] - tin[x] + 1);
	mid = (depth[ord[lg[mid]][tin[x]]] < depth[ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]] ? ord[lg[mid]][tin[x]]: ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]);
//	cerr << x - 1 << " " << y - 1 << " " << mid - 1 << "\n";
	return dp[x] + dp[y] - 2 * dp[mid];
}

void Init(int N2, int A[], int B[], int D[]) {
	for(int i = 2;i < N * 4;i++)
		lg[i] = lg[i / 2] + 1;
	n = N2;
	for(int i = 0;i < n - 1;i++){
		g[A[i] + 1].push_back(MP(B[i] + 1, D[i]));
		g[B[i] + 1].push_back(MP(A[i] + 1, D[i]));
	}
	cent(1, 0);
	dfs_prep(1, 1);
	for(int i = 1;i <= 20;i++)
		for(int j = 1;j + (1 << i) - 1 <= timer;j++)
			ord[i][j] = (depth[ord[i - 1][j]] < depth[ord[i - 1][j + (1 << (i - 1))]] ? ord[i - 1][j]: ord[i - 1][j + (1 << (i - 1))]);
}

long long Query(int S, int X[], int T, int Y[]) {
//	cerr << "NEXT\n";
	ll ans = INF;
 	Q++;
 	for(int i = 0;i < S;i++){
		X[i]++;
		int j = X[i];
		while(j){
			if(last_used[j] != Q)
				last_used[j] = Q, mcost[j] = INF;
			mcost[j] = min(mcost[j], calc(j, X[i]));
		//	cerr << j - 1 << " " << X[i - 1] << " " << calc(j, X[i]) << "\n";
			j = cent_pr[j];
		}
  	}
  	for(int i = 0;i < T;i++){
  		Y[i]++;
  		int j = Y[i];
  		while(j){
  			if(last_used[j] != Q)
  				last_used[j] = Q, mcost[j] = INF;
  			ans = min(ans, mcost[j] + calc(j, Y[i]));
  		//	cerr << j - 1 << " " << Y[i] - 1 << " " << ans << " " << mcost[j] << " " << calc(j, Y[i]) << "\n";
  			j = cent_pr[j];
  		}
  	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 20716 KB Output is correct
2 Correct 523 ms 38508 KB Output is correct
3 Correct 740 ms 38560 KB Output is correct
4 Correct 686 ms 38660 KB Output is correct
5 Correct 687 ms 38892 KB Output is correct
6 Correct 317 ms 38636 KB Output is correct
7 Correct 701 ms 38632 KB Output is correct
8 Correct 696 ms 38632 KB Output is correct
9 Correct 697 ms 38944 KB Output is correct
10 Correct 370 ms 38560 KB Output is correct
11 Correct 687 ms 38572 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20332 KB Output is correct
2 Correct 3054 ms 165928 KB Output is correct
3 Correct 4436 ms 167668 KB Output is correct
4 Correct 1109 ms 166320 KB Output is correct
5 Correct 5593 ms 196844 KB Output is correct
6 Correct 4700 ms 169836 KB Output is correct
7 Correct 2666 ms 66280 KB Output is correct
8 Correct 638 ms 66912 KB Output is correct
9 Correct 2809 ms 70752 KB Output is correct
10 Correct 2613 ms 67692 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 20716 KB Output is correct
2 Correct 523 ms 38508 KB Output is correct
3 Correct 740 ms 38560 KB Output is correct
4 Correct 686 ms 38660 KB Output is correct
5 Correct 687 ms 38892 KB Output is correct
6 Correct 317 ms 38636 KB Output is correct
7 Correct 701 ms 38632 KB Output is correct
8 Correct 696 ms 38632 KB Output is correct
9 Correct 697 ms 38944 KB Output is correct
10 Correct 370 ms 38560 KB Output is correct
11 Correct 687 ms 38572 KB Output is correct
12 Correct 18 ms 20332 KB Output is correct
13 Correct 3054 ms 165928 KB Output is correct
14 Correct 4436 ms 167668 KB Output is correct
15 Correct 1109 ms 166320 KB Output is correct
16 Correct 5593 ms 196844 KB Output is correct
17 Correct 4700 ms 169836 KB Output is correct
18 Correct 2666 ms 66280 KB Output is correct
19 Correct 638 ms 66912 KB Output is correct
20 Correct 2809 ms 70752 KB Output is correct
21 Correct 2613 ms 67692 KB Output is correct
22 Correct 4360 ms 153836 KB Output is correct
23 Correct 4508 ms 176000 KB Output is correct
24 Correct 6641 ms 175848 KB Output is correct
25 Correct 6472 ms 179424 KB Output is correct
26 Correct 6678 ms 175852 KB Output is correct
27 Correct 7708 ms 199508 KB Output is correct
28 Correct 1439 ms 176772 KB Output is correct
29 Correct 6787 ms 175536 KB Output is correct
30 Correct 6731 ms 174856 KB Output is correct
31 Correct 6656 ms 175596 KB Output is correct
32 Correct 2751 ms 71692 KB Output is correct
33 Correct 602 ms 67424 KB Output is correct
34 Correct 1830 ms 64108 KB Output is correct
35 Correct 1886 ms 63980 KB Output is correct
36 Correct 2457 ms 64596 KB Output is correct
37 Correct 2572 ms 64752 KB Output is correct