oj.uz

Submission #59228

# Submission time Handle Problem Language Result Execution time Memory
59228 2018-07-21T09:34:25 Z gusfring Factories (JOI14_factories) C++14
33 / 100
 8000 ms 518552 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 28 ms 12664 KB Output is correct
2 Correct 482 ms 30768 KB Output is correct
3 Correct 427 ms 40300 KB Output is correct
4 Correct 500 ms 49808 KB Output is correct
5 Correct 498 ms 59664 KB Output is correct
6 Correct 377 ms 68424 KB Output is correct
7 Correct 522 ms 78292 KB Output is correct
8 Correct 488 ms 87972 KB Output is correct
9 Correct 468 ms 97552 KB Output is correct
10 Correct 300 ms 106324 KB Output is correct
11 Correct 470 ms 116168 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 116168 KB Output is correct
2 Correct 3683 ms 230692 KB Output is correct
3 Correct 5144 ms 265460 KB Output is correct
4 Correct 1101 ms 265460 KB Output is correct
5 Correct 7381 ms 322912 KB Output is correct
6 Correct 5157 ms 322912 KB Output is correct
7 Correct 1776 ms 322912 KB Output is correct
8 Correct 510 ms 322912 KB Output is correct
9 Correct 1923 ms 322912 KB Output is correct
10 Correct 1699 ms 322912 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12664 KB Output is correct
2 Correct 482 ms 30768 KB Output is correct
3 Correct 427 ms 40300 KB Output is correct
4 Correct 500 ms 49808 KB Output is correct
5 Correct 498 ms 59664 KB Output is correct
6 Correct 377 ms 68424 KB Output is correct
7 Correct 522 ms 78292 KB Output is correct
8 Correct 488 ms 87972 KB Output is correct
9 Correct 468 ms 97552 KB Output is correct
10 Correct 300 ms 106324 KB Output is correct
11 Correct 470 ms 116168 KB Output is correct
12 Correct 16 ms 116168 KB Output is correct
13 Correct 3683 ms 230692 KB Output is correct
14 Correct 5144 ms 265460 KB Output is correct
15 Correct 1101 ms 265460 KB Output is correct
16 Correct 7381 ms 322912 KB Output is correct
17 Correct 5157 ms 322912 KB Output is correct
18 Correct 1776 ms 322912 KB Output is correct
19 Correct 510 ms 322912 KB Output is correct
20 Correct 1923 ms 322912 KB Output is correct
21 Correct 1699 ms 322912 KB Output is correct
22 Correct 3985 ms 382848 KB Output is correct
23 Correct 3985 ms 411824 KB Output is correct
24 Correct 7135 ms 450044 KB Output is correct
25 Correct 6692 ms 474820 KB Output is correct
26 Correct 6497 ms 489956 KB Output is correct
27 Execution timed out 8083 ms 518552 KB Time limit exceeded
28 Halted 0 ms 0 KB -