oj.uz

Submission #222029

# Submission time Handle Problem Language Result Execution time Memory
222029 2020-04-12T00:37:20 Z Dan13llljws Factories (JOI14_factories) C++14
100 / 100
 4993 ms 176064 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int, int> pii;
#define ms(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define f first
#define s second
const int mod = 1e9 + 7, base = 131, MM = 5e5 + 5, LG = 25;
int n, dep[MM], w[MM], pre[MM]; bool vis[MM];
ll dist[LG][MM], ans[MM];
vector<pii> adj[MM]; vector<int> clr;
void get_weight(int src, int par){
	w[src] = 1;
	for (auto v : adj[src]){
		if (v.s == par || vis[v.s]) continue;
		get_weight(v.s, src);
		w[src] += w[v.s];
	}
}
int get_cent(int src, int par, int wt){
	for (auto v : adj[src])
		if (v.s != par && !vis[v.s] && w[v.s] * 2 > wt)
			return get_cent(v.s, src, wt);
	return src;
}
void dfs(int src, int par, ll d, int lvl){
	dist[lvl][src] = d;
	for (auto v : adj[src]){
		if (v.s == par || vis[v.s]) continue;
		dfs(v.s, src, d + v.f, lvl);
	}
}
void decomp(int src, int lvl){
	dfs(src, src, 0, lvl);
	vis[src] = 1;
	for (auto v : adj[src]){
		if (vis[v.s]) continue;
		get_weight(v.s, src);
		int rt = get_cent(v.s, src, w[v.s]);
		pre[rt] = src, dep[rt] = lvl + 1;
		decomp(rt, lvl + 1);
	}
}
void Init(int N, int A[], int B[], int D[]){
	n = N;
	for (int i = 0; i < N - 1; i++){
		A[i]++, B[i]++;
		adj[A[i]].pb({D[i], B[i]});
		adj[B[i]].pb({D[i], A[i]});
	}	
	get_weight(1, 1);
	decomp(get_cent(1, 1, N), 0);
	ms(ans, INF);
}
long long Query(int S, int X[], int T, int Y[]){
	for (int i = 0; i < S; i++)
		for (int src = X[i] + 1, l = dep[src], tmp = src; l >= 0; l--, tmp = pre[tmp]){
			if (ans[tmp] == LLINF) clr.pb(tmp);
			ans[tmp] = min(ans[tmp], dist[l][src]);
		}
	ll ret = LLINF;
	for (int i = 0; i < T; i++)
		for (int src = Y[i] + 1, l = dep[src], tmp = src; l >= 0; l--, tmp = pre[tmp])
			ret = min(ret, dist[l][src] + ans[tmp]);
	for (int p : clr) ans[p] = LLINF;
	clr.clear();
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16632 KB Output is correct
2 Correct 378 ms 34424 KB Output is correct
3 Correct 413 ms 34488 KB Output is correct
4 Correct 390 ms 34432 KB Output is correct
5 Correct 422 ms 34808 KB Output is correct
6 Correct 331 ms 33912 KB Output is correct
7 Correct 405 ms 34544 KB Output is correct
8 Correct 407 ms 34428 KB Output is correct
9 Correct 420 ms 34808 KB Output is correct
10 Correct 333 ms 34040 KB Output is correct
11 Correct 406 ms 34552 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16256 KB Output is correct
2 Correct 2073 ms 131588 KB Output is correct
3 Correct 3177 ms 147944 KB Output is correct
4 Correct 795 ms 80732 KB Output is correct
5 Correct 4403 ms 171384 KB Output is correct
6 Correct 3318 ms 149888 KB Output is correct
7 Correct 1160 ms 59232 KB Output is correct
8 Correct 486 ms 48236 KB Output is correct
9 Correct 1350 ms 63172 KB Output is correct
10 Correct 1141 ms 60788 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16632 KB Output is correct
2 Correct 378 ms 34424 KB Output is correct
3 Correct 413 ms 34488 KB Output is correct
4 Correct 390 ms 34432 KB Output is correct
5 Correct 422 ms 34808 KB Output is correct
6 Correct 331 ms 33912 KB Output is correct
7 Correct 405 ms 34544 KB Output is correct
8 Correct 407 ms 34428 KB Output is correct
9 Correct 420 ms 34808 KB Output is correct
10 Correct 333 ms 34040 KB Output is correct
11 Correct 406 ms 34552 KB Output is correct
12 Correct 15 ms 16256 KB Output is correct
13 Correct 2073 ms 131588 KB Output is correct
14 Correct 3177 ms 147944 KB Output is correct
15 Correct 795 ms 80732 KB Output is correct
16 Correct 4403 ms 171384 KB Output is correct
17 Correct 3318 ms 149888 KB Output is correct
18 Correct 1160 ms 59232 KB Output is correct
19 Correct 486 ms 48236 KB Output is correct
20 Correct 1350 ms 63172 KB Output is correct
21 Correct 1141 ms 60788 KB Output is correct
22 Correct 2462 ms 138408 KB Output is correct
23 Correct 2587 ms 143312 KB Output is correct
24 Correct 3823 ms 156816 KB Output is correct
25 Correct 3735 ms 160552 KB Output is correct
26 Correct 3834 ms 156368 KB Output is correct
27 Correct 4993 ms 176064 KB Output is correct
28 Correct 1004 ms 91872 KB Output is correct
29 Correct 3854 ms 155940 KB Output is correct
30 Correct 3817 ms 155324 KB Output is correct
31 Correct 3832 ms 156200 KB Output is correct
32 Correct 1212 ms 64500 KB Output is correct
33 Correct 490 ms 49128 KB Output is correct
34 Correct 787 ms 54520 KB Output is correct
35 Correct 803 ms 54648 KB Output is correct
36 Correct 1008 ms 57592 KB Output is correct
37 Correct 1033 ms 57720 KB Output is correct