oj.uz

Submission #113518

# Submission time Handle Problem Language Result Execution time Memory
113518 2019-05-26T05:02:18 Z AngusRitossa Factories (JOI14_factories) C++14
100 / 100
 4568 ms 220836 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
typedef long long ll;
int n;
vector<pair<int, int> > adj[500010];
int iscentroid[500010];
int sz[500010];
ll closest[500010];
pair<int, ll> mycentroids[500010][19];
int findsz(int a, int p = -1)
{
	sz[a] = 1;
	for (auto b : adj[a])
	{
		if (b.first != p && !iscentroid[b.first]) sz[a] += findsz(b.first, a);
	}
	return sz[a];
}	
ll len = 0;
int dfslen(int a, int c, int p = -1, ll len = 0)
{
	mycentroids[a][iscentroid[c]-1] = { c, len };
	D("%d belongs to %d, dis %lld\n", a, c, len);
	sz[a] = 1;
	for (auto b : adj[a])
	{
		if (!iscentroid[b.first] && b.first != p)
		{
			sz[a] += dfslen(b.first, c, a, len+b.second);
		}
	}
	return sz[a];
}
void findcentroid(int a, int upto = 1, int above = 0, int p = -1)
{
	int sumchildren = above+1;
	pair<int, int> mxchild = { 0, 0 };
	for (auto b : adj[a])
	{
		if (b.first != p && !iscentroid[b.first])
		{
			mxchild = max(mxchild, { sz[b.first], b.first } );
			sumchildren += sz[b.first];
		}
	}
	if (mxchild.first <= (sumchildren)/2)
	{
		// is a centroid
		iscentroid[a] = upto;
		dfslen(a, a);
		for (auto b : adj[a])
		{
			if (!iscentroid[b.first]) findcentroid(b.first, upto+1);
		}
		return;
	}
	findcentroid(mxchild.second, upto, sumchildren-mxchild.first, a);
}
 
void Init(int N, int A[], int B[], int D[]) 
{
	n = N;
	for (int i = 0; i < n-1; i++)
	{
		adj[A[i]].emplace_back(B[i], D[i]);
		adj[B[i]].emplace_back(A[i], D[i]);
	}
	for (int i = 0; i < n; i++) fill_n(mycentroids[i], 19, make_pair(0, 1e15));
	findsz(0);
	findcentroid(0);
	fill_n(closest, n, 1e15);
}
ll Query(int s, int x[], int t, int y[]) 
{
	ll ans = 1e15;
	for (int i = 0; i < s; i++) for (int j = 0; j < 19; j++) 
	{
		auto c = mycentroids[x[i]][j];
		closest[c.first] = min(closest[c.first], c.second);
	}
	for (int i = 0; i < t; i++) for (int j = 0; j < 19; j++) 
	{
		auto c = mycentroids[y[i]][j];
		ans = min(ans, closest[c.first]+c.second);
	}
	for (int i = 0; i < s; i++) for (int j = 0; j < 19; j++) 
	{
		auto c = mycentroids[x[i]][j];
		closest[c.first] = 1e15;
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12544 KB Output is correct
2 Correct 359 ms 21924 KB Output is correct
3 Correct 354 ms 21928 KB Output is correct
4 Correct 352 ms 22032 KB Output is correct
5 Correct 392 ms 22220 KB Output is correct
6 Correct 352 ms 22104 KB Output is correct
7 Correct 335 ms 21912 KB Output is correct
8 Correct 340 ms 22008 KB Output is correct
9 Correct 338 ms 22136 KB Output is correct
10 Correct 347 ms 22008 KB Output is correct
11 Correct 346 ms 22008 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12416 KB Output is correct
2 Correct 2054 ms 200280 KB Output is correct
3 Correct 2844 ms 200984 KB Output is correct
4 Correct 1180 ms 201068 KB Output is correct
5 Correct 3867 ms 217616 KB Output is correct
6 Correct 2900 ms 202388 KB Output is correct
7 Correct 1083 ms 57976 KB Output is correct
8 Correct 929 ms 58888 KB Output is correct
9 Correct 1173 ms 62428 KB Output is correct
10 Correct 1172 ms 59384 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12544 KB Output is correct
2 Correct 359 ms 21924 KB Output is correct
3 Correct 354 ms 21928 KB Output is correct
4 Correct 352 ms 22032 KB Output is correct
5 Correct 392 ms 22220 KB Output is correct
6 Correct 352 ms 22104 KB Output is correct
7 Correct 335 ms 21912 KB Output is correct
8 Correct 340 ms 22008 KB Output is correct
9 Correct 338 ms 22136 KB Output is correct
10 Correct 347 ms 22008 KB Output is correct
11 Correct 346 ms 22008 KB Output is correct
12 Correct 13 ms 12416 KB Output is correct
13 Correct 2054 ms 200280 KB Output is correct
14 Correct 2844 ms 200984 KB Output is correct
15 Correct 1180 ms 201068 KB Output is correct
16 Correct 3867 ms 217616 KB Output is correct
17 Correct 2900 ms 202388 KB Output is correct
18 Correct 1083 ms 57976 KB Output is correct
19 Correct 929 ms 58888 KB Output is correct
20 Correct 1173 ms 62428 KB Output is correct
21 Correct 1172 ms 59384 KB Output is correct
22 Correct 2970 ms 201656 KB Output is correct
23 Correct 2883 ms 204092 KB Output is correct
24 Correct 3891 ms 203432 KB Output is correct
25 Correct 3791 ms 206456 KB Output is correct
26 Correct 3371 ms 202896 KB Output is correct
27 Correct 4568 ms 220836 KB Output is correct
28 Correct 2088 ms 204880 KB Output is correct
29 Correct 3433 ms 203020 KB Output is correct
30 Correct 3378 ms 203148 KB Output is correct
31 Correct 3268 ms 203184 KB Output is correct
32 Correct 1395 ms 62840 KB Output is correct
33 Correct 1212 ms 59280 KB Output is correct
34 Correct 1041 ms 56312 KB Output is correct
35 Correct 991 ms 56440 KB Output is correct
36 Correct 1141 ms 56716 KB Output is correct
37 Correct 1118 ms 56824 KB Output is correct