oj.uz

Submission #56996

# Submission time Handle Problem Language Result Execution time Memory
56996 2018-07-13T13:06:46 Z RezwanArefin01 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 504180 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

typedef long long ll; 

const int MAX = 5e5 + 10; 
vector<int> adj[MAX], cost[MAX]; 
int lvl[MAX], sub[MAX], p[MAX], vis[MAX];
ll d[20][MAX], ans[MAX];
	
void calc(int u, int par) { sub[u] = 1; 
	for(int v : adj[u]) if(v - par && !vis[v]) 
		calc(v, u), sub[u] += sub[v];
}
int centroid(int u, int par, int r) {
	for(int v : adj[u]) if(v - par && !vis[v]) 
		if(sub[v] > r) return centroid(v, u, r);
	return u;
}
void dfs(int l, int u, int par, int pcost) {
	if(par + 1) d[l][u] = d[l][par] + pcost; 
	for(int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i], c = cost[u][i]; 
		if(v == par || vis[v]) continue; 
		dfs(l, v, u, c); 
	}
}
void decompose(int u, int par) {
	calc(u, -1);
	int c = centroid(u, -1, sub[u] >> 1);
	vis[c] = 1, p[c] = par; 
	if(par + 1) lvl[c] = lvl[par] + 1;
	dfs(lvl[c], c, -1, 0);
	for(int v : adj[c]) if(v - par && !vis[v]) 
		decompose(v, c);
}

void update(int u) {
	for(int v = u; v + 1; v = p[v]) 
		ans[v] = min(ans[v], d[lvl[v]][u]);
}
ll query(int u) {
	ll ret = 1e18;
	for(int v = u; v + 1; v = p[v])
		ret = min(ret, ans[v] + d[lvl[v]][u]);
	return ret;
}


void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N - 1; i++) {
		int u = A[i], v = B[i], c = D[i];
		adj[u].push_back(v);
		adj[v].push_back(u); 
		cost[u].push_back(c); 
		cost[v].push_back(c); 
	}
	for(int i = 0; i < N; i++) 
		ans[i] = 1e18; 
	decompose(0, -1); 
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i++) 
		update(X[i]); 
	ll ret = 1e18; 
	for(int i = 0; i < T; i++) 
		ret = min(ret, query(Y[i])); 
	for(int i = 0; i < S; i++) {
		for(int v = X[i]; v + 1; v = p[v]) 
			ans[v] = 1e18; 
	} return ret; 
}

Compilation message

factories.cpp: In function 'void dfs(int, int, int, int)':
factories.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24440 KB Output is correct
2 Correct 407 ms 42688 KB Output is correct
3 Correct 480 ms 52204 KB Output is correct
4 Correct 489 ms 61828 KB Output is correct
5 Correct 480 ms 71620 KB Output is correct
6 Correct 394 ms 80436 KB Output is correct
7 Correct 508 ms 90284 KB Output is correct
8 Correct 430 ms 99732 KB Output is correct
9 Correct 511 ms 109452 KB Output is correct
10 Correct 311 ms 118320 KB Output is correct
11 Correct 532 ms 128184 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 128184 KB Output is correct
2 Correct 3150 ms 244304 KB Output is correct
3 Correct 4297 ms 274016 KB Output is correct
4 Correct 1136 ms 274016 KB Output is correct
5 Correct 5748 ms 327676 KB Output is correct
6 Correct 4463 ms 327676 KB Output is correct
7 Correct 1732 ms 327676 KB Output is correct
8 Correct 609 ms 327676 KB Output is correct
9 Correct 1515 ms 327676 KB Output is correct
10 Correct 1357 ms 327676 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24440 KB Output is correct
2 Correct 407 ms 42688 KB Output is correct
3 Correct 480 ms 52204 KB Output is correct
4 Correct 489 ms 61828 KB Output is correct
5 Correct 480 ms 71620 KB Output is correct
6 Correct 394 ms 80436 KB Output is correct
7 Correct 508 ms 90284 KB Output is correct
8 Correct 430 ms 99732 KB Output is correct
9 Correct 511 ms 109452 KB Output is correct
10 Correct 311 ms 118320 KB Output is correct
11 Correct 532 ms 128184 KB Output is correct
12 Correct 24 ms 128184 KB Output is correct
13 Correct 3150 ms 244304 KB Output is correct
14 Correct 4297 ms 274016 KB Output is correct
15 Correct 1136 ms 274016 KB Output is correct
16 Correct 5748 ms 327676 KB Output is correct
17 Correct 4463 ms 327676 KB Output is correct
18 Correct 1732 ms 327676 KB Output is correct
19 Correct 609 ms 327676 KB Output is correct
20 Correct 1515 ms 327676 KB Output is correct
21 Correct 1357 ms 327676 KB Output is correct
22 Correct 3928 ms 376564 KB Output is correct
23 Correct 3658 ms 398300 KB Output is correct
24 Correct 6076 ms 432304 KB Output is correct
25 Correct 5479 ms 452140 KB Output is correct
26 Correct 6397 ms 466532 KB Output is correct
27 Execution timed out 8102 ms 504180 KB Time limit exceeded
28 Halted 0 ms 0 KB -