oj.uz

Submission #387713

# Submission time Handle Problem Language Result Execution time Memory
387713 2021-04-09T06:13:38 Z wind_reaper Factories (JOI14_factories) C++17
100 / 100
 6975 ms 225272 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
	#include "factories.h"
#endif
 
using namespace std;
 
const int MXN = 500000;
const int lg = 20;
const int64_t INF = 1e18;

vector<int64_t> dist[MXN];

int par[MXN], sz[MXN], r[MXN];
int64_t best[MXN];

vector<array<int, 2>> g[MXN];
 
int hit[10*MXN], ptr = 0;
 
int dfs(int node, int p){ 
	sz[node] = 1;
 
	for(auto& [v, d] : g[node]){
		if(v == p)
			continue;
		sz[node] += dfs(v, node);
	}
 
 	return sz[node];
}

void comp(int node, int p){
	int64_t d = dist[node].back();
	for(auto& [v, di] : g[node]){
		if(!r[v] && v != p){
			dist[v].push_back(d+int64_t(di));
			comp(v, node);
		}
	}
}

void decompose(int node, int p){
	int inv = -1, ms = sz[node] >> 1;
	
	for(auto& [v, d] : g[node])
		if(!r[v] && sz[v] > ms){
			inv = v;
			break;
		}
 
	if(inv != -1){
		sz[node] -= sz[inv];
		sz[inv] += sz[node];
		return decompose(inv, p); 
	}
 
	r[node] = 1;
	par[node] = p;
	
	dist[node].push_back(0);
	comp(node, node);

	for(auto& [v, d] : g[node])
		if(!r[v])
			decompose(v, node); 
}
 
inline void update(int node){
	int v = node, pt = dist[node].size() - 1;
	while(v != -1){
		best[v] = min(best[v], dist[node][pt--]);
		hit[ptr++] = v;
		v = par[v];
	}
}

inline int64_t query(int node){
	int64_t ans = INF;
	int v = node, pt = dist[node].size() - 1;
	while(v != -1){
		ans = min(ans, best[v] + dist[node][pt--]);
		v = par[v];
	}
	return ans;
}

void Init(int n, int A[], int B[], int D[]){
	for(int i = 0; i < n-1; i++){
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
 
	// memset(par, -1, sizeof par);
	
	for(int i = 0; i < n; i++)
		best[i] = INF;
 
	dfs(0, 0);
	decompose(0, -1);
}

long long Query(int S, int X[], int T, int Y[]){
	ptr = 0;
 
	for(int i = 0; i < S; i++)
		update(X[i]);

	int64_t ans = INF;

	for(int i = 0; i < T; i++)
		ans = min(ans, query(Y[i]));

	for(int i = 0; i < ptr; i++)
		best[hit[i]] = INF;

	return ans;
}

#ifdef LOCAL
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 

	int N, Q;
	cin >> N >> Q;
	int A[N-1], B[N-1], D[N-1];

	for(int i = 0; i < N-1; i++){
		cin >> A[i] >> B[i] >> D[i];
	}

	Init(N, A, B, D);

	for(int i = 0; i < Q; i++){
		int S, T;
		cin >> S >> T;
		int X[S], Y[T];
		for(int j = 0; j < S; j++)
			cin >> X[j];
		for(int j = 0; j < T; j++)
			cin >> Y[j];
 
		cout << Query(S, X, T, Y) << '\n';
	}

	return 0; 
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24140 KB Output is correct
2 Correct 353 ms 32576 KB Output is correct
3 Correct 396 ms 32792 KB Output is correct
4 Correct 387 ms 32916 KB Output is correct
5 Correct 417 ms 33228 KB Output is correct
6 Correct 275 ms 32288 KB Output is correct
7 Correct 392 ms 32812 KB Output is correct
8 Correct 400 ms 32900 KB Output is correct
9 Correct 421 ms 33220 KB Output is correct
10 Correct 283 ms 32408 KB Output is correct
11 Correct 391 ms 32900 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23884 KB Output is correct
2 Correct 3186 ms 131568 KB Output is correct
3 Correct 4344 ms 168076 KB Output is correct
4 Correct 1055 ms 81880 KB Output is correct
5 Correct 5544 ms 224052 KB Output is correct
6 Correct 4344 ms 169504 KB Output is correct
7 Correct 1335 ms 68600 KB Output is correct
8 Correct 554 ms 58156 KB Output is correct
9 Correct 1675 ms 78028 KB Output is correct
10 Correct 1500 ms 70120 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24140 KB Output is correct
2 Correct 353 ms 32576 KB Output is correct
3 Correct 396 ms 32792 KB Output is correct
4 Correct 387 ms 32916 KB Output is correct
5 Correct 417 ms 33228 KB Output is correct
6 Correct 275 ms 32288 KB Output is correct
7 Correct 392 ms 32812 KB Output is correct
8 Correct 400 ms 32900 KB Output is correct
9 Correct 421 ms 33220 KB Output is correct
10 Correct 283 ms 32408 KB Output is correct
11 Correct 391 ms 32900 KB Output is correct
12 Correct 16 ms 23884 KB Output is correct
13 Correct 3186 ms 131568 KB Output is correct
14 Correct 4344 ms 168076 KB Output is correct
15 Correct 1055 ms 81880 KB Output is correct
16 Correct 5544 ms 224052 KB Output is correct
17 Correct 4344 ms 169504 KB Output is correct
18 Correct 1335 ms 68600 KB Output is correct
19 Correct 554 ms 58156 KB Output is correct
20 Correct 1675 ms 78028 KB Output is correct
21 Correct 1500 ms 70120 KB Output is correct
22 Correct 3571 ms 134540 KB Output is correct
23 Correct 3870 ms 139652 KB Output is correct
24 Correct 5450 ms 173004 KB Output is correct
25 Correct 5170 ms 176676 KB Output is correct
26 Correct 5487 ms 170532 KB Output is correct
27 Correct 6975 ms 225272 KB Output is correct
28 Correct 1355 ms 110484 KB Output is correct
29 Correct 5656 ms 193932 KB Output is correct
30 Correct 5388 ms 193468 KB Output is correct
31 Correct 5258 ms 194100 KB Output is correct
32 Correct 1723 ms 81700 KB Output is correct
33 Correct 552 ms 58992 KB Output is correct
34 Correct 1110 ms 64100 KB Output is correct
35 Correct 1235 ms 64592 KB Output is correct
36 Correct 1466 ms 67184 KB Output is correct
37 Correct 1541 ms 67100 KB Output is correct