oj.uz

Submission #161947

# Submission time Handle Problem Language Result Execution time Memory
161947 2019-11-05T11:26:44 Z nvmdava Factories (JOI14_factories) C++17
100 / 100
 6285 ms 346888 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)
			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){
			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)
			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])
			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);
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24440 KB Output is correct
2 Correct 436 ms 40160 KB Output is correct
3 Correct 469 ms 40696 KB Output is correct
4 Correct 455 ms 40696 KB Output is correct
5 Correct 487 ms 41208 KB Output is correct
6 Correct 336 ms 39748 KB Output is correct
7 Correct 555 ms 40648 KB Output is correct
8 Correct 473 ms 40696 KB Output is correct
9 Correct 486 ms 41024 KB Output is correct
10 Correct 361 ms 39748 KB Output is correct
11 Correct 505 ms 40584 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 3014 ms 200948 KB Output is correct
3 Correct 4550 ms 271576 KB Output is correct
4 Correct 1246 ms 95008 KB Output is correct
5 Correct 5725 ms 346588 KB Output is correct
6 Correct 4561 ms 272248 KB Output is correct
7 Correct 1389 ms 75512 KB Output is correct
8 Correct 557 ms 52580 KB Output is correct
9 Correct 1521 ms 89852 KB Output is correct
10 Correct 1329 ms 76748 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24440 KB Output is correct
2 Correct 436 ms 40160 KB Output is correct
3 Correct 469 ms 40696 KB Output is correct
4 Correct 455 ms 40696 KB Output is correct
5 Correct 487 ms 41208 KB Output is correct
6 Correct 336 ms 39748 KB Output is correct
7 Correct 555 ms 40648 KB Output is correct
8 Correct 473 ms 40696 KB Output is correct
9 Correct 486 ms 41024 KB Output is correct
10 Correct 361 ms 39748 KB Output is correct
11 Correct 505 ms 40584 KB Output is correct
12 Correct 25 ms 24056 KB Output is correct
13 Correct 3014 ms 200948 KB Output is correct
14 Correct 4550 ms 271576 KB Output is correct
15 Correct 1246 ms 95008 KB Output is correct
16 Correct 5725 ms 346588 KB Output is correct
17 Correct 4561 ms 272248 KB Output is correct
18 Correct 1389 ms 75512 KB Output is correct
19 Correct 557 ms 52580 KB Output is correct
20 Correct 1521 ms 89852 KB Output is correct
21 Correct 1329 ms 76748 KB Output is correct
22 Correct 3366 ms 200468 KB Output is correct
23 Correct 3470 ms 205288 KB Output is correct
24 Correct 5409 ms 273048 KB Output is correct
25 Correct 5162 ms 276824 KB Output is correct
26 Correct 5286 ms 273988 KB Output is correct
27 Correct 6285 ms 346888 KB Output is correct
28 Correct 1405 ms 98772 KB Output is correct
29 Correct 5148 ms 272952 KB Output is correct
30 Correct 5087 ms 273280 KB Output is correct
31 Correct 5028 ms 272944 KB Output is correct
32 Correct 1507 ms 88712 KB Output is correct
33 Correct 556 ms 51556 KB Output is correct
34 Correct 1052 ms 67116 KB Output is correct
35 Correct 1091 ms 67960 KB Output is correct
36 Correct 1449 ms 72968 KB Output is correct
37 Correct 1342 ms 73064 KB Output is correct