oj.uz

Submission #113514

# Submission time Handle Problem Language Result Execution time Memory
113514 2019-05-26T04:35:11 Z AngusRitossa Factories (JOI14_factories) C++14
100 / 100
 5792 ms 225416 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 upto;
int sz[500010];
ll closest[500010];
pair<int, ll> mycentroids[500010][20];
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;
void 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);
	for (auto b : adj[a])
	{
		if (!iscentroid[b.first] && b.first != p)
		{
			dfslen(b.first, c, a, len+b.second);
		}
	}
}
void findcentroid(int a, int upto = 1, int above = 0, int p = -1)
{
	if (!above) findsz(a);
	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], 20, make_pair(0, 1e15));
	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 < 20; 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 < 20; 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 < 20; 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 19 ms 12800 KB Output is correct
2 Correct 345 ms 22776 KB Output is correct
3 Correct 348 ms 22776 KB Output is correct
4 Correct 345 ms 22904 KB Output is correct
5 Correct 356 ms 23176 KB Output is correct
6 Correct 353 ms 22908 KB Output is correct
7 Correct 349 ms 22792 KB Output is correct
8 Correct 342 ms 22904 KB Output is correct
9 Correct 349 ms 22972 KB Output is correct
10 Correct 350 ms 22776 KB Output is correct
11 Correct 355 ms 22904 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12416 KB Output is correct
2 Correct 2343 ms 208600 KB Output is correct
3 Correct 3529 ms 208732 KB Output is correct
4 Correct 1213 ms 208960 KB Output is correct
5 Correct 4510 ms 225416 KB Output is correct
6 Correct 3600 ms 210072 KB Output is correct
7 Correct 1191 ms 59640 KB Output is correct
8 Correct 883 ms 60548 KB Output is correct
9 Correct 1127 ms 63000 KB Output is correct
10 Correct 1156 ms 60920 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12800 KB Output is correct
2 Correct 345 ms 22776 KB Output is correct
3 Correct 348 ms 22776 KB Output is correct
4 Correct 345 ms 22904 KB Output is correct
5 Correct 356 ms 23176 KB Output is correct
6 Correct 353 ms 22908 KB Output is correct
7 Correct 349 ms 22792 KB Output is correct
8 Correct 342 ms 22904 KB Output is correct
9 Correct 349 ms 22972 KB Output is correct
10 Correct 350 ms 22776 KB Output is correct
11 Correct 355 ms 22904 KB Output is correct
12 Correct 14 ms 12416 KB Output is correct
13 Correct 2343 ms 208600 KB Output is correct
14 Correct 3529 ms 208732 KB Output is correct
15 Correct 1213 ms 208960 KB Output is correct
16 Correct 4510 ms 225416 KB Output is correct
17 Correct 3600 ms 210072 KB Output is correct
18 Correct 1191 ms 59640 KB Output is correct
19 Correct 883 ms 60548 KB Output is correct
20 Correct 1127 ms 63000 KB Output is correct
21 Correct 1156 ms 60920 KB Output is correct
22 Correct 3105 ms 209756 KB Output is correct
23 Correct 3059 ms 211956 KB Output is correct
24 Correct 4368 ms 210912 KB Output is correct
25 Correct 4563 ms 214120 KB Output is correct
26 Correct 4181 ms 210880 KB Output is correct
27 Correct 5792 ms 225020 KB Output is correct
28 Correct 2025 ms 212608 KB Output is correct
29 Correct 4021 ms 210528 KB Output is correct
30 Correct 3907 ms 210424 KB Output is correct
31 Correct 3926 ms 210772 KB Output is correct
32 Correct 1712 ms 63608 KB Output is correct
33 Correct 1291 ms 61064 KB Output is correct
34 Correct 1145 ms 58104 KB Output is correct
35 Correct 1161 ms 57992 KB Output is correct
36 Correct 1194 ms 58332 KB Output is correct
37 Correct 1265 ms 58272 KB Output is correct