oj.uz

Submission #585947

# Submission time Handle Problem Language Result Execution time Memory
585947 2022-06-29T15:13:49 Z M_W Factories (JOI14_factories) C++17
100 / 100
 4682 ms 186712 KB 
#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int sz[500005], lvl[500005], pa[500005];
bool blocked[500005];
vector<ii> adj[500005];
long long dist[21][500005];

// Centroid

void dfs(int a, int p){
	sz[a] = 1;
	for(auto [x, w]: adj[a]){
		if(blocked[x] || x == p) continue;
		dfs(x, a);
		sz[a] += sz[x];
	}
}

void dfs_dis(int a, int p, int lv){
	for(auto [x, w] : adj[a]){
		if(x == p || blocked[x]) continue;
		dist[lv][x] = dist[lv][a] + w;
		dfs_dis(x, a, lv);
	}
}

void dec(int a, int p){
	dfs(a, a);
	int cur = a, prev = -1;
	while(true){
		int mx = -1, ch;
		for(auto [x, w] : adj[cur]){
			if(blocked[x] || x == prev) continue;
			if(sz[x] > mx){
				mx = sz[x];
				ch = x;
			}
		}
		if(mx * 2 > sz[a]){
			prev = cur;
			cur = ch;
		}
		else break;
	}
	lvl[cur] = p == -1 ? 0 : lvl[p] + 1;
	dfs_dis(cur, cur, lvl[cur]);
	blocked[cur] = true;
	
	pa[cur] = p;
	for(auto [x, w] : adj[cur]) if(!blocked[x]) dec(x, cur);
}

long long val[500005];

void Init(int N, int A[], int B[], int D[]){
	for(int i = 0; i < N - 1; i++){
		adj[A[i]].push_back({B[i], D[i] * 1ll});
		adj[B[i]].push_back({A[i], D[i] * 1ll});
	}
	dec(0, -1);
	for(int i = 0; i < N; i++) val[i] = 1e15;
}

void upd(int u){
	int old_u = u;
	for(; u != -1; u = pa[u]){
		val[u] = min(val[u], dist[lvl[u]][old_u]);
	}
}

long long query(int u){
	long long res = 1e15;
	int old_u = u;
	for(; u != -1; u = pa[u]){
		res = min(res, val[u] + dist[lvl[u]][old_u]);
	}
	return res;
}

void reset(int u){
	for(; u != -1; u = pa[u]) val[u] = 1e15;
}

long long Query(int S, int X[], int T, int Y[]) {
	long long res = 1e15;
	for(int i = 0; i < S; i++) upd(X[i]);
	for(int i = 0; i < T; i++) res = min(res, query(Y[i]));
	for(int i = 0; i < S; i++) reset(X[i]);
	
	return res;
}

Compilation message

factories.cpp: In function 'void dec(int, int)':
factories.cpp:51:49: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |  for(auto [x, w] : adj[cur]) if(!blocked[x]) dec(x, cur);
      |                                              ~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12628 KB Output is correct
2 Correct 267 ms 30352 KB Output is correct
3 Correct 286 ms 30592 KB Output is correct
4 Correct 308 ms 30476 KB Output is correct
5 Correct 300 ms 30924 KB Output is correct
6 Correct 191 ms 30012 KB Output is correct
7 Correct 318 ms 30512 KB Output is correct
8 Correct 279 ms 30548 KB Output is correct
9 Correct 335 ms 30852 KB Output is correct
10 Correct 203 ms 29960 KB Output is correct
11 Correct 292 ms 30500 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12324 KB Output is correct
2 Correct 1738 ms 134740 KB Output is correct
3 Correct 2811 ms 152972 KB Output is correct
4 Correct 560 ms 80748 KB Output is correct
5 Correct 3725 ms 184280 KB Output is correct
6 Correct 2843 ms 155152 KB Output is correct
7 Correct 864 ms 56936 KB Output is correct
8 Correct 280 ms 45012 KB Output is correct
9 Correct 1020 ms 61796 KB Output is correct
10 Correct 815 ms 58420 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12628 KB Output is correct
2 Correct 267 ms 30352 KB Output is correct
3 Correct 286 ms 30592 KB Output is correct
4 Correct 308 ms 30476 KB Output is correct
5 Correct 300 ms 30924 KB Output is correct
6 Correct 191 ms 30012 KB Output is correct
7 Correct 318 ms 30512 KB Output is correct
8 Correct 279 ms 30548 KB Output is correct
9 Correct 335 ms 30852 KB Output is correct
10 Correct 203 ms 29960 KB Output is correct
11 Correct 292 ms 30500 KB Output is correct
12 Correct 10 ms 12324 KB Output is correct
13 Correct 1738 ms 134740 KB Output is correct
14 Correct 2811 ms 152972 KB Output is correct
15 Correct 560 ms 80748 KB Output is correct
16 Correct 3725 ms 184280 KB Output is correct
17 Correct 2843 ms 155152 KB Output is correct
18 Correct 864 ms 56936 KB Output is correct
19 Correct 280 ms 45012 KB Output is correct
20 Correct 1020 ms 61796 KB Output is correct
21 Correct 815 ms 58420 KB Output is correct
22 Correct 2340 ms 140704 KB Output is correct
23 Correct 2424 ms 145456 KB Output is correct
24 Correct 3914 ms 161064 KB Output is correct
25 Correct 3747 ms 165028 KB Output is correct
26 Correct 3605 ms 161260 KB Output is correct
27 Correct 4682 ms 186712 KB Output is correct
28 Correct 708 ms 90980 KB Output is correct
29 Correct 3819 ms 160800 KB Output is correct
30 Correct 3800 ms 160160 KB Output is correct
31 Correct 3674 ms 160872 KB Output is correct
32 Correct 1065 ms 62872 KB Output is correct
33 Correct 282 ms 45440 KB Output is correct
34 Correct 670 ms 51860 KB Output is correct
35 Correct 628 ms 52076 KB Output is correct
36 Correct 874 ms 55280 KB Output is correct
37 Correct 811 ms 55428 KB Output is correct