oj.uz

Submission #354337

# Submission time Handle Problem Language Result Execution time Memory
354337 2021-01-21T18:34:27 Z Kenzo_1114 Factories (JOI14_factories) C++17
100 / 100
 6400 ms 207980 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MAXN = 500010;
const int MAXK = 21;
const long long int INF = 2e18;

int n, q, n_cur, sub[MAXN], par[MAXN], depth[MAXN];
long long int dist[MAXK][MAXN], s[MAXN];
vector<int> graph[MAXN], cost[MAXN];
bool marc[MAXN];

void find_sub(int v, int p)
{
	sub[v] = 1;
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p || marc[u])	continue;
		find_sub(u, v), sub[v] += sub[u];
	}
}

int find_centroid(int v, int p)
{
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p || marc[u])	continue;
		if(2 * sub[u] >= n_cur)	return find_centroid(u, v);
	}

	return v;
}

void find_dist(int v, int p, int l, long long int d)
{
	dist[l][v] = d;
//	printf("dist[%d][%d] = %lld\n", l, v, dist[l][v]);
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		int w = cost[v][i];
		if(u == p || marc[u])	continue;
		find_dist(u, v, l, d + w);	
	}
}

void decompose(int v, int p, int level)
{
	find_sub(v, p);
	n_cur = sub[v];
	int centroid = find_centroid(v, p);

//	printf("centroid = %d\n", centroid);
	marc[centroid] = true;
	par[centroid] = (v == p) ? centroid : p;
	depth[centroid] = level;

	find_dist(centroid, centroid, level, 0);

	for(int i = 0; i < (int) graph[centroid].size(); i++)
	{
		int u = graph[centroid][i];
		if(!marc[u])	decompose(u, centroid, level + 1);
	}
}

void Init(int N, int A[], int B[], int D[])
{
	n = N;
	for(int i = 0; i < n; i++)	s[i] = INF;

	for(int i = 0; i < n - 1; i++)
	{
		int a = A[i], b = B[i], d = D[i];
		graph[a].push_back(b);
		graph[b].push_back(a);
		cost[a].push_back(d);
		cost[b].push_back(d);
	}

	decompose(0, 0, 0);
}

void upd(int v, bool flag)
{
	int cur = v;

	if(flag)	s[cur] = 0;
	else		s[cur] = INF;
	
	while(cur != par[cur])
	{
		cur = par[cur];
		if(flag)	s[cur] = min(s[cur], dist[depth[cur]][v]);
		else		s[cur] = INF;
	}
}

long long int qry(int v)
{
	int cur = v;
	long long int ans = s[cur];

	while(cur != par[cur])
	{
		cur = par[cur];
		ans = min(ans, s[cur] + dist[depth[cur]][v]);
	}

	return ans;
}

long long int Query(int S, int X[], int T, int Y[])
{
	for(int i = 0; i < S; i++)	upd(X[i], true);
	
	long long int ans = INF;
	for(int i = 0; i < T; i++)	ans = min(ans, qry(Y[i]));
	for(int i = 0; i < S; i++)	upd(X[i], false);

	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24300 KB Output is correct
2 Correct 374 ms 32868 KB Output is correct
3 Correct 420 ms 33004 KB Output is correct
4 Correct 412 ms 32876 KB Output is correct
5 Correct 439 ms 33280 KB Output is correct
6 Correct 312 ms 32556 KB Output is correct
7 Correct 410 ms 33004 KB Output is correct
8 Correct 409 ms 33092 KB Output is correct
9 Correct 442 ms 33260 KB Output is correct
10 Correct 295 ms 32492 KB Output is correct
11 Correct 409 ms 33004 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24044 KB Output is correct
2 Correct 2799 ms 138260 KB Output is correct
3 Correct 4131 ms 155948 KB Output is correct
4 Correct 954 ms 90024 KB Output is correct
5 Correct 5347 ms 186592 KB Output is correct
6 Correct 4170 ms 157112 KB Output is correct
7 Correct 1311 ms 57024 KB Output is correct
8 Correct 452 ms 46044 KB Output is correct
9 Correct 1581 ms 61612 KB Output is correct
10 Correct 1334 ms 58208 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24300 KB Output is correct
2 Correct 374 ms 32868 KB Output is correct
3 Correct 420 ms 33004 KB Output is correct
4 Correct 412 ms 32876 KB Output is correct
5 Correct 439 ms 33280 KB Output is correct
6 Correct 312 ms 32556 KB Output is correct
7 Correct 410 ms 33004 KB Output is correct
8 Correct 409 ms 33092 KB Output is correct
9 Correct 442 ms 33260 KB Output is correct
10 Correct 295 ms 32492 KB Output is correct
11 Correct 409 ms 33004 KB Output is correct
12 Correct 19 ms 24044 KB Output is correct
13 Correct 2799 ms 138260 KB Output is correct
14 Correct 4131 ms 155948 KB Output is correct
15 Correct 954 ms 90024 KB Output is correct
16 Correct 5347 ms 186592 KB Output is correct
17 Correct 4170 ms 157112 KB Output is correct
18 Correct 1311 ms 57024 KB Output is correct
19 Correct 452 ms 46044 KB Output is correct
20 Correct 1581 ms 61612 KB Output is correct
21 Correct 1334 ms 58208 KB Output is correct
22 Correct 3294 ms 138780 KB Output is correct
23 Correct 3494 ms 167788 KB Output is correct
24 Correct 5122 ms 181748 KB Output is correct
25 Correct 5147 ms 185724 KB Output is correct
26 Correct 5076 ms 182024 KB Output is correct
27 Correct 6400 ms 207980 KB Output is correct
28 Correct 1117 ms 118604 KB Output is correct
29 Correct 5006 ms 181692 KB Output is correct
30 Correct 4961 ms 181056 KB Output is correct
31 Correct 4913 ms 181844 KB Output is correct
32 Correct 1472 ms 76652 KB Output is correct
33 Correct 468 ms 60548 KB Output is correct
34 Correct 943 ms 65772 KB Output is correct
35 Correct 973 ms 66096 KB Output is correct
36 Correct 1267 ms 69140 KB Output is correct
37 Correct 1288 ms 69228 KB Output is correct