oj.uz

Submission #161943

# Submission time Handle Problem Language Result Execution time Memory
161943 2019-11-05T11:20:27 Z nvmdava Factories (JOI14_factories) C++17
100 / 100
 6135 ms 346716 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
using namespace std;
#define M 500005

pair<int, ll> d[M];

bool act[M];
vector<pair<int, ll> > cen[M], adj[M];

void dfs3(int root, int v, int p = -1, ll d = 0){
	cen[v].push_back({root, d});
	for(auto& x : adj[v]){
		int u = x.ff;
		if(act[u] || p == u)
			continue;
		dfs3(root, u, v, d + x.ss);
	}
}

int q = M;

int sz[M];

void dfs1(int v, int p = -1){
	sz[v] = 1;
	for(auto& x : adj[v]){
		int u = x.ff;
		if(act[u] || p == u)
			continue;
		dfs1(u, v);
		sz[v] += sz[u];
	}
}

int dfs2(int v, int p, int s){
	for(auto& x : adj[v]){
		int u = x.ff;
		if(act[u] || p == u)
			continue;
		if(sz[u] > s)
			return dfs2(u, v, s);
	}
	return v;
}

void decomp(int v){
	dfs1(v);
	v = dfs2(v, -1, sz[v] / 2);
	dfs3(v, v);
	act[v] = 1;
	for(auto& x : adj[v]){
		if(act[x.ff])
			continue;
		decomp(x.ff);
	}
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N; i++)
		d[i] = {q, 0};
	
	for(int i = 0; i < N - 1; i++){
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}

	decomp(0);
}

long long Query(int S, int X[], int T, int Y[]) {
	--q;
	ll res = 0x3f3f3f3f3f3f3f3f;
	for(int i = 0; i < S; i++){
		for(auto& x : cen[X[i]]){
			d[x.ff] = min(d[x.ff], {q, x.ss});
		}
	}
	for(int i = 0; i < T; i++){
		for(auto& x : cen[Y[i]]){
			if(d[x.ff].ff == q)
				res = min(res, d[x.ff].ss + x.ss);
			else
				break;
		}
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24440 KB Output is correct
2 Correct 432 ms 42616 KB Output is correct
3 Correct 460 ms 43128 KB Output is correct
4 Correct 430 ms 43000 KB Output is correct
5 Correct 487 ms 43392 KB Output is correct
6 Correct 339 ms 41976 KB Output is correct
7 Correct 459 ms 43000 KB Output is correct
8 Correct 596 ms 43156 KB Output is correct
9 Correct 480 ms 43436 KB Output is correct
10 Correct 333 ms 42104 KB Output is correct
11 Correct 459 ms 43176 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24056 KB Output is correct
2 Correct 2820 ms 200312 KB Output is correct
3 Correct 4434 ms 271232 KB Output is correct
4 Correct 1153 ms 94776 KB Output is correct
5 Correct 5541 ms 346128 KB Output is correct
6 Correct 4752 ms 272052 KB Output is correct
7 Correct 1278 ms 78404 KB Output is correct
8 Correct 587 ms 55524 KB Output is correct
9 Correct 1450 ms 92216 KB Output is correct
10 Correct 1285 ms 79480 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24440 KB Output is correct
2 Correct 432 ms 42616 KB Output is correct
3 Correct 460 ms 43128 KB Output is correct
4 Correct 430 ms 43000 KB Output is correct
5 Correct 487 ms 43392 KB Output is correct
6 Correct 339 ms 41976 KB Output is correct
7 Correct 459 ms 43000 KB Output is correct
8 Correct 596 ms 43156 KB Output is correct
9 Correct 480 ms 43436 KB Output is correct
10 Correct 333 ms 42104 KB Output is correct
11 Correct 459 ms 43176 KB Output is correct
12 Correct 25 ms 24056 KB Output is correct
13 Correct 2820 ms 200312 KB Output is correct
14 Correct 4434 ms 271232 KB Output is correct
15 Correct 1153 ms 94776 KB Output is correct
16 Correct 5541 ms 346128 KB Output is correct
17 Correct 4752 ms 272052 KB Output is correct
18 Correct 1278 ms 78404 KB Output is correct
19 Correct 587 ms 55524 KB Output is correct
20 Correct 1450 ms 92216 KB Output is correct
21 Correct 1285 ms 79480 KB Output is correct
22 Correct 3349 ms 200368 KB Output is correct
23 Correct 3304 ms 205024 KB Output is correct
24 Correct 5127 ms 272840 KB Output is correct
25 Correct 5027 ms 276560 KB Output is correct
26 Correct 5417 ms 273784 KB Output is correct
27 Correct 6135 ms 346716 KB Output is correct
28 Correct 1475 ms 98684 KB Output is correct
29 Correct 5023 ms 272696 KB Output is correct
30 Correct 5015 ms 273168 KB Output is correct
31 Correct 4992 ms 272928 KB Output is correct
32 Correct 1513 ms 88760 KB Output is correct
33 Correct 564 ms 51784 KB Output is correct
34 Correct 1065 ms 67024 KB Output is correct
35 Correct 1091 ms 67836 KB Output is correct
36 Correct 1361 ms 72876 KB Output is correct
37 Correct 1318 ms 72904 KB Output is correct