oj.uz

Submission #26580

# Submission time Handle Problem Language Result Execution time Memory
26580 2017-07-03T09:32:32 Z rubabredwan Factories (JOI14_factories) C++14
100 / 100
 5826 ms 205268 KB 
/*  Bismillahir Rahmanir Rahim  */
 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
typedef pair <int, int> pii;
 
const int N = 500005;
const long long oo = 1e18;
 
vector < vector <pii>> g(N);
vector < int > e[N];
long long mn[N], dis[N];
long long pre[N][25], idx[N];
int n, anc[N], sub[N], vis[N];	

void dfs(int at, int par){
	pre[at][++idx[at]] = dis[at];
	sub[at] = 1;
	for(auto u : g[at]){
		if(vis[u.first] || u.first == par) continue;
		dis[u.first] = dis[at] + u.second;
		dfs(u.first, at);
		sub[at] += sub[u.first];
	}
}

void decompose(int at, int par, int tot){
	int cen = 0, mx = -1;
	for(auto u : g[at]){
		if(vis[u.first] || sub[u.first] > sub[at]) continue;
		if(sub[u.first] > mx){
			cen = u.first;
			mx = sub[cen];
		}
	}
	if(mx <= tot / 2){
		if(par){
			anc[at] = par;
		}
		tot = 0;
		vis[at] = 1;
		dis[at] = 0;
		dfs(at, at);
		for(auto u : g[at]){
			if(!vis[u.first]){ 
				decompose(u.first, at, sub[u.first]);
			}
		}
	}
	else decompose(cen, par, tot);
}

long long Query(int S, int X[], int T, int Y[]){	
	int cur, from, j;
	for(int i = 0; i < S; ++i){
		cur = X[i] + 1, from = X[i] + 1, j = 1;
		for(j = idx[from]; j; --j){
			mn[cur] = min(mn[cur], pre[from][j]);
			cur = anc[cur];
		}
	}
	long long ret = oo;
	for(int i = 0; i < T; ++i){
		cur = Y[i] + 1, from = Y[i] + 1, j = 1;
		for(j = idx[from]; j; --j){
			ret = min(ret, pre[from][j] + mn[cur]);
			cur = anc[cur];
		}
	}
	for(int i = 0; i < S; ++i){
		cur = X[i] + 1;
		while(cur) mn[cur] = oo, cur = anc[cur];
	}
	return ret;
}
 
void Init(int N, int A[], int B[], int D[]){
	n = N;
	for(int i = 0; i < N - 1; ++i){
		g[A[i] + 1].push_back({B[i] + 1, D[i]});
		g[B[i] + 1].push_back({A[i] + 1, D[i]});
	}
	memset(idx, -1, sizeof(idx));
	dfs(1, 0);
	decompose(1, 0, sub[1]);
	for(int i = 1; i <= n; ++i) mn[i] = oo;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 162964 KB Output is correct
2 Correct 353 ms 163228 KB Output is correct
3 Correct 423 ms 163228 KB Output is correct
4 Correct 419 ms 163228 KB Output is correct
5 Correct 426 ms 163248 KB Output is correct
6 Correct 399 ms 163264 KB Output is correct
7 Correct 476 ms 163228 KB Output is correct
8 Correct 426 ms 163228 KB Output is correct
9 Correct 373 ms 163248 KB Output is correct
10 Correct 349 ms 163264 KB Output is correct
11 Correct 396 ms 163228 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 162964 KB Output is correct
2 Correct 3516 ms 181708 KB Output is correct
3 Correct 4006 ms 184696 KB Output is correct
4 Correct 1253 ms 182676 KB Output is correct
5 Correct 5249 ms 205268 KB Output is correct
6 Correct 4503 ms 184268 KB Output is correct
7 Correct 1456 ms 167204 KB Output is correct
8 Correct 443 ms 167196 KB Output is correct
9 Correct 1459 ms 169256 KB Output is correct
10 Correct 1339 ms 167112 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3539 ms 181708 KB Output is correct
2 Correct 3546 ms 181708 KB Output is correct
3 Correct 4579 ms 183708 KB Output is correct
4 Correct 5059 ms 184284 KB Output is correct
5 Correct 4839 ms 184144 KB Output is correct
6 Correct 5826 ms 199488 KB Output is correct
7 Correct 1703 ms 182676 KB Output is correct
8 Correct 4789 ms 183776 KB Output is correct
9 Correct 3666 ms 183252 KB Output is correct
10 Correct 4096 ms 183820 KB Output is correct
11 Correct 1343 ms 169740 KB Output is correct
12 Correct 439 ms 167196 KB Output is correct
13 Correct 669 ms 166660 KB Output is correct
14 Correct 649 ms 166660 KB Output is correct
15 Correct 993 ms 167112 KB Output is correct
16 Correct 1049 ms 167100 KB Output is correct