oj.uz

Submission #169670

# Submission time Handle Problem Language Result Execution time Memory
169670 2019-12-22T04:00:59 Z oolimry Factories (JOI14_factories) C++14
100 / 100
 5230 ms 347172 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> ii;
static vector<ii> adj[500005];
static vector<ii> parent[500005];
static long long dis[500005];
static int sz[500005];
static bool cented[500005];

static long long shortest[500005];
 
vector<int> nodes;
void dfs(int u){
	sz[u] = 1;
	nodes.push_back(u);
	for(ii v : adj[u]){
		if(sz[v.first] == 0 && !cented[v.first]){
			dis[v.first] = dis[u] + v.second;
			dfs(v.first);
			sz[u] += sz[v.first];
		}
	}
}

void recurse(int r, int p){
	nodes.clear();
	dfs(r);
	
	int centroid;
	for(int u : nodes){
		int big = sz[r] - sz[u];
		for(ii v : adj[u]){
			if(!cented[v.first] && sz[v.first] < sz[u]){
				big = max(big, sz[v.first]);
			}
		}
		if(2*big <= sz[r]){
			centroid = u;
			break;
		} 
	}

	for(int u : nodes){
		sz[u] = 0;
		if(p != -1) parent[u].push_back(ii(p,dis[u]));
		dis[u] = 0;
	}
	cented[centroid] = true;
	for(ii v : adj[centroid]){
		dis[v.first] = v.second;
		if(!cented[v.first]) recurse(v.first, centroid);
	}
}

const long long inf = 12381293928390122LL;
void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0;i < N-1;i++){
		int u = A[i];
		int v = B[i];
		int w = D[i];
		adj[u].push_back(ii(v,w));
		adj[v].push_back(ii(u,w));
	}
	recurse(0,-1);
	for(int i = 0;i < N;i++){
		reverse(parent[i].begin(),parent[i].end());
	}
	fill(shortest,shortest+N,inf);
}

long long Query(int S, int X[], int T, int Y[]) {
	
	long long ans = inf;
	for(int i = 0;i < S;i++){
		int u = X[i];
		shortest[u] = 0;
		for(ii v : parent[u]){
			shortest[v.first] = min(shortest[v.first],v.second);
		}
	}
	
	for(int i = 0;i < T;i++){
		int u = Y[i];
		ans = min(ans, shortest[u]);
		for(ii v : parent[u]){
			ans = min(ans, shortest[v.first] + v.second);
		}
	}
	
	for(int i = 0;i < S;i++){
		int u = X[i];
		shortest[u] = inf;
		for(ii v : parent[u]){
			shortest[v.first] = inf;
		}
	}
	
	return ans;
}

Compilation message

factories.cpp: In function 'void recurse(int, int)':
factories.cpp:31:6: warning: 'centroid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int centroid;
      ^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24184 KB Output is correct
2 Correct 429 ms 42624 KB Output is correct
3 Correct 443 ms 43000 KB Output is correct
4 Correct 467 ms 43112 KB Output is correct
5 Correct 486 ms 43336 KB Output is correct
6 Correct 339 ms 41848 KB Output is correct
7 Correct 457 ms 42880 KB Output is correct
8 Correct 470 ms 43128 KB Output is correct
9 Correct 507 ms 43308 KB Output is correct
10 Correct 338 ms 41928 KB Output is correct
11 Correct 442 ms 42880 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 2655 ms 210344 KB Output is correct
3 Correct 3979 ms 253940 KB Output is correct
4 Correct 1026 ms 106368 KB Output is correct
5 Correct 4520 ms 342296 KB Output is correct
6 Correct 4022 ms 255828 KB Output is correct
7 Correct 1260 ms 83676 KB Output is correct
8 Correct 557 ms 59764 KB Output is correct
9 Correct 1417 ms 87192 KB Output is correct
10 Correct 1245 ms 85192 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24184 KB Output is correct
2 Correct 429 ms 42624 KB Output is correct
3 Correct 443 ms 43000 KB Output is correct
4 Correct 467 ms 43112 KB Output is correct
5 Correct 486 ms 43336 KB Output is correct
6 Correct 339 ms 41848 KB Output is correct
7 Correct 457 ms 42880 KB Output is correct
8 Correct 470 ms 43128 KB Output is correct
9 Correct 507 ms 43308 KB Output is correct
10 Correct 338 ms 41928 KB Output is correct
11 Correct 442 ms 42880 KB Output is correct
12 Correct 25 ms 24056 KB Output is correct
13 Correct 2655 ms 210344 KB Output is correct
14 Correct 3979 ms 253940 KB Output is correct
15 Correct 1026 ms 106368 KB Output is correct
16 Correct 4520 ms 342296 KB Output is correct
17 Correct 4022 ms 255828 KB Output is correct
18 Correct 1260 ms 83676 KB Output is correct
19 Correct 557 ms 59764 KB Output is correct
20 Correct 1417 ms 87192 KB Output is correct
21 Correct 1245 ms 85192 KB Output is correct
22 Correct 3238 ms 214704 KB Output is correct
23 Correct 3374 ms 221492 KB Output is correct
24 Correct 4715 ms 261728 KB Output is correct
25 Correct 4839 ms 266060 KB Output is correct
26 Correct 4400 ms 262948 KB Output is correct
27 Correct 5230 ms 347172 KB Output is correct
28 Correct 1526 ms 116748 KB Output is correct
29 Correct 4477 ms 262372 KB Output is correct
30 Correct 4545 ms 261864 KB Output is correct
31 Correct 4950 ms 262432 KB Output is correct
32 Correct 1648 ms 87988 KB Output is correct
33 Correct 761 ms 60148 KB Output is correct
34 Correct 1109 ms 73592 KB Output is correct
35 Correct 1060 ms 74484 KB Output is correct
36 Correct 1296 ms 82196 KB Output is correct
37 Correct 1313 ms 82024 KB Output is correct