oj.uz

Submission #97118

# Submission time Handle Problem Language Result Execution time Memory
97118 2019-02-14T02:12:48 Z luciocf Factories (JOI14_factories) C++14
100 / 100
 7196 ms 175280 KB 
#include <bits/stdc++.h>
#include "factories.h"

#define ff first
#define ss second

using namespace std;

const int maxn = 5e5+10;
const long long inf = 1e18+10;

typedef pair<int, int> pii;
typedef long long ll;

int n;
int sz[maxn], pai[maxn], nivel[maxn];

ll dist[maxn][19], child[maxn];

bool mark[maxn];

vector<pii> grafo[maxn];

int dfs(int u, int p)
{
	sz[u] = 1;
	for (auto v: grafo[u])
		if (v.first != p && !mark[v.first])
			sz[u] += dfs(v.first, u);

	return sz[u];
}

int centroid(int S, int u, int p)
{
	for (auto v: grafo[u])
		if (v.first != p && !mark[v.first] && sz[v.first] > S/2)
			return centroid(S, v.first, u);

	return u;
}

void upd(int u, int p, int lvl, ll d)
{	
	dist[u][lvl] = d;

	for (auto v: grafo[u])
		if (v.first != p && !mark[v.first])
			upd(v.first, u, lvl, d+(ll)v.second);
}

int decompose(int u, int lvl)
{
	dfs(u, -1);

	int c = centroid(sz[u], u, -1);
	mark[c] = 1, nivel[c] = lvl;

	upd(c, -1, lvl, 0LL);

	for (auto v: grafo[c])
	{
		if (mark[v.first]) continue;

		int c2 = decompose(v.first, lvl+1);
		
		pai[c2] = c;
	}

	return c;
}

void Init(int N, int A[], int B[], int D[])
{
	n = N;

	for (int i = 0; i < n-1; i++)
	{
		grafo[A[i]].push_back({B[i], D[i]});
		grafo[B[i]].push_back({A[i], D[i]});
	}

	memset(pai, -1, sizeof pai);

	for (int i = 0; i < n; i++)
		child[i] = inf;

	decompose(0, 0);
}

long long Query(int S, int X[], int T, int Y[])
{
	int s = S, t = T;

	vector<int> vis;

	for (int i = 0; i < t; i++)
	{
		int v = Y[i];
		
		while (v != -1)
		{
			vis.push_back(v);

			child[v] = min(child[v], dist[Y[i]][nivel[v]]);

			v = pai[v];
		}
	}

	ll ans = inf;

	for (int i = 0; i < s; i++)
	{
		int v = X[i];

		while (v != -1)
		{
			ans = min(ans, dist[X[i]][nivel[v]]+child[v]);

			v = pai[v];
		}
	}

	for (auto x: vis) child[x] = inf;

	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14592 KB Output is correct
2 Correct 352 ms 24176 KB Output is correct
3 Correct 350 ms 23928 KB Output is correct
4 Correct 433 ms 23956 KB Output is correct
5 Correct 395 ms 24220 KB Output is correct
6 Correct 401 ms 23940 KB Output is correct
7 Correct 401 ms 23800 KB Output is correct
8 Correct 405 ms 24252 KB Output is correct
9 Correct 390 ms 24140 KB Output is correct
10 Correct 332 ms 23800 KB Output is correct
11 Correct 405 ms 23896 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14208 KB Output is correct
2 Correct 3261 ms 128280 KB Output is correct
3 Correct 4766 ms 128820 KB Output is correct
4 Correct 1277 ms 147552 KB Output is correct
5 Correct 7181 ms 164464 KB Output is correct
6 Correct 5128 ms 149264 KB Output is correct
7 Correct 1500 ms 59116 KB Output is correct
8 Correct 662 ms 60148 KB Output is correct
9 Correct 1650 ms 62820 KB Output is correct
10 Correct 1458 ms 60540 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14592 KB Output is correct
2 Correct 352 ms 24176 KB Output is correct
3 Correct 350 ms 23928 KB Output is correct
4 Correct 433 ms 23956 KB Output is correct
5 Correct 395 ms 24220 KB Output is correct
6 Correct 401 ms 23940 KB Output is correct
7 Correct 401 ms 23800 KB Output is correct
8 Correct 405 ms 24252 KB Output is correct
9 Correct 390 ms 24140 KB Output is correct
10 Correct 332 ms 23800 KB Output is correct
11 Correct 405 ms 23896 KB Output is correct
12 Correct 18 ms 14208 KB Output is correct
13 Correct 3261 ms 128280 KB Output is correct
14 Correct 4766 ms 128820 KB Output is correct
15 Correct 1277 ms 147552 KB Output is correct
16 Correct 7181 ms 164464 KB Output is correct
17 Correct 5128 ms 149264 KB Output is correct
18 Correct 1500 ms 59116 KB Output is correct
19 Correct 662 ms 60148 KB Output is correct
20 Correct 1650 ms 62820 KB Output is correct
21 Correct 1458 ms 60540 KB Output is correct
22 Correct 3875 ms 157956 KB Output is correct
23 Correct 4057 ms 156944 KB Output is correct
24 Correct 6230 ms 162568 KB Output is correct
25 Correct 6162 ms 164380 KB Output is correct
26 Correct 5380 ms 155516 KB Output is correct
27 Correct 7196 ms 175280 KB Output is correct
28 Correct 1583 ms 158680 KB Output is correct
29 Correct 5546 ms 155256 KB Output is correct
30 Correct 5597 ms 155100 KB Output is correct
31 Correct 5506 ms 155400 KB Output is correct
32 Correct 1677 ms 68400 KB Output is correct
33 Correct 668 ms 60612 KB Output is correct
34 Correct 1104 ms 57376 KB Output is correct
35 Correct 1039 ms 57164 KB Output is correct
36 Correct 1229 ms 57724 KB Output is correct
37 Correct 1205 ms 57484 KB Output is correct