oj.uz

Submission #29215

# Submission time Handle Problem Language Result Execution time Memory
29215 2017-07-18T18:07:20 Z Bruteforceman Factories (JOI14_factories) C++11
33 / 100
 6000 ms 190132 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
const int logn = 25;
int sub[500010];
long long dp[logn][500010];

int deg[500010];
long long dis[500010];
vector <pii> g[500010];
bool vis[500010];

int anc[500010];
long long aux[500010];
const long long inf = 1e16;

void subtree(int x, int par) {
	sub[x] = 1;
	for(auto i : g[x]) {
		if(i.first != par && vis[i.first] == false) {
			subtree(i.first, x);
			sub[x] += sub[i.first];
		}
	}
}
int centroid(int x, int par, int range) {
	for(auto i : g[x]) {
		if(i.first != par && vis[i.first] == false) {
			if(sub[i.first] > range) return centroid(i.first, x, range); 
		}
	}
	return x;
}

void dfs(int x, int par, int level) {
	assert(level < logn);
	dp[level][x] = dis[x];
	for(auto i : g[x]) {
		if(i.first != par && vis[i.first] == false) {
			dis[i.first] = i.second + dis[x];
			dfs(i.first, x, level);
		}
	}
}

void create(int x, int par, int level) {
	subtree(x, -1);
	int c = centroid(x, -1, sub[x] >> 1);
 	dis[c] = 0;
	dfs(c, -1, level);
	deg[c] = level;
	vis[c] = true;
	anc[c] = par;
	for(auto i : g[c]) {
		if(vis[i.first] == false) {	
			create(i.first, c, level + 1);
		}
	}
}
void put(int x) {
	int cur = x;
	int lev = deg[x];
	while(cur >= 0) {
		aux[cur] = min(aux[cur], dp[lev][x]);
		cur = anc[cur];
		--lev;
	}
}
void remove(int x) {
	int cur = x;
	while(cur >= 0) {
		aux[cur] = inf;
		cur = anc[cur];
	} 
}
long long get(int x) {
	int cur = x;
	long long ans = inf;
	int lev = deg[x];
	while(cur >= 0) {
		ans = min(ans, dp[lev][x] + aux[cur]);
		cur = anc[cur];
		--lev;
	}
	return ans;
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N-1; i++) {
		g[A[i]].push_back(pii(B[i], D[i]));
		g[B[i]].push_back(pii(A[i], D[i]));
	}
	create(0, -1, 0);
	for(int i = 0; i < N; i++) {
		aux[i] = inf;
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i++) {
		put(X[i]);
	}
	long long ans = inf;
	for(int i = 0; i < T; i++) {
		ans = min(ans, get(Y[i]));
	}
	for(int i = 0; i < S; i++) {
		remove(X[i]);
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 147828 KB Output is correct
2 Correct 366 ms 148092 KB Output is correct
3 Correct 389 ms 148092 KB Output is correct
4 Correct 416 ms 148092 KB Output is correct
5 Correct 533 ms 148112 KB Output is correct
6 Correct 333 ms 148128 KB Output is correct
7 Correct 426 ms 148092 KB Output is correct
8 Correct 399 ms 148092 KB Output is correct
9 Correct 453 ms 148112 KB Output is correct
10 Correct 359 ms 148128 KB Output is correct
11 Correct 526 ms 148092 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 147828 KB Output is correct
2 Correct 3146 ms 166572 KB Output is correct
3 Correct 4663 ms 169560 KB Output is correct
4 Correct 736 ms 167540 KB Output is correct
5 Correct 5586 ms 190132 KB Output is correct
6 Correct 5046 ms 169132 KB Output is correct
7 Correct 1499 ms 152072 KB Output is correct
8 Correct 433 ms 152060 KB Output is correct
9 Correct 1359 ms 154120 KB Output is correct
10 Correct 1413 ms 151976 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3739 ms 166572 KB Output is correct
2 Correct 3976 ms 166572 KB Output is correct
3 Execution timed out 6000 ms 168576 KB Execution timed out
4 Halted 0 ms 0 KB -