oj.uz

Submission #354336

# Submission time Handle Problem Language Result Execution time Memory
354336 2021-01-21T18:29:46 Z Kenzo_1114 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 224816 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];
vector<int> graph[MAXN], cost[MAXN];
set<long long int> s[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 - 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].insert(0);
	else		s[cur].clear();
	
	while(cur != par[cur])
	{
		cur = par[cur];
		if(flag)	s[cur].insert(dist[depth[cur]][v]);
		else		s[cur].clear();
	}
}

long long int qry(int v)
{
	int cur = v;
	long long int ans = (s[cur].empty()) ? INF : *s[cur].begin();

	while(cur != par[cur])
	{
		cur = par[cur];
		ans = min(ans, (s[cur].empty()) ? INF : *s[cur].begin() + 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 49 ms 47980 KB Output is correct
2 Correct 1362 ms 66328 KB Output is correct
3 Correct 1444 ms 66028 KB Output is correct
4 Correct 2366 ms 67732 KB Output is correct
5 Correct 2329 ms 67112 KB Output is correct
6 Correct 542 ms 65544 KB Output is correct
7 Correct 1395 ms 66168 KB Output is correct
8 Correct 1667 ms 66192 KB Output is correct
9 Correct 2341 ms 67172 KB Output is correct
10 Correct 526 ms 65660 KB Output is correct
11 Correct 1416 ms 66352 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47596 KB Output is correct
2 Correct 3748 ms 176632 KB Output is correct
3 Correct 5420 ms 193304 KB Output is correct
4 Correct 1148 ms 127960 KB Output is correct
5 Correct 6923 ms 224816 KB Output is correct
6 Correct 5641 ms 195396 KB Output is correct
7 Correct 3507 ms 93660 KB Output is correct
8 Correct 696 ms 82908 KB Output is correct
9 Correct 3949 ms 98432 KB Output is correct
10 Correct 3244 ms 94728 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47980 KB Output is correct
2 Correct 1362 ms 66328 KB Output is correct
3 Correct 1444 ms 66028 KB Output is correct
4 Correct 2366 ms 67732 KB Output is correct
5 Correct 2329 ms 67112 KB Output is correct
6 Correct 542 ms 65544 KB Output is correct
7 Correct 1395 ms 66168 KB Output is correct
8 Correct 1667 ms 66192 KB Output is correct
9 Correct 2341 ms 67172 KB Output is correct
10 Correct 526 ms 65660 KB Output is correct
11 Correct 1416 ms 66352 KB Output is correct
12 Correct 32 ms 47596 KB Output is correct
13 Correct 3748 ms 176632 KB Output is correct
14 Correct 5420 ms 193304 KB Output is correct
15 Correct 1148 ms 127960 KB Output is correct
16 Correct 6923 ms 224816 KB Output is correct
17 Correct 5641 ms 195396 KB Output is correct
18 Correct 3507 ms 93660 KB Output is correct
19 Correct 696 ms 82908 KB Output is correct
20 Correct 3949 ms 98432 KB Output is correct
21 Correct 3244 ms 94728 KB Output is correct
22 Execution timed out 8101 ms 205072 KB Time limit exceeded
23 Halted 0 ms 0 KB -