oj.uz

Submission #26551

# Submission time Handle Problem Language Result Execution time Memory
26551 2017-07-02T18:20:59 Z rubabredwan Factories (JOI14_factories) C++14
15 / 100
 6000 ms 200068 KB 
/*  Bismillahir Rahmanir Rahim  */
 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
typedef pair <int, long long> pii;
 
const int N = 500005;
const long long oo = 1e18;
 
vector < vector <pii>> g(N);
int n;
int tot;
int sub[N];
int anc[N];
int vis[N];
int lst[N], t;
long long mn[N];
long long pre[N][25];
int idx[N];
 
void dfs0(int at, int par){
	++tot;
	sub[at] = 1;
	for(auto u : g[at]){
		if(vis[u.first] || u.first == par) continue;
		dfs0(u.first, at);
		sub[at] += sub[u.first];
	}
}
 
int get(int at, int par){
	for(auto u : g[at]){
		if(vis[u.first] || u.first == par) continue;
		if(sub[u.first] >= tot / 2) return get(u.first, at);
	}
	return at;
}
 
void get_dis(int at, int par, long long dis){
	pre[at][++idx[at]] = dis;
	for(auto u : g[at]){
		if(vis[u.first] || u.first == par) continue;
		get_dis(u.first, at, dis + u.second);
	}
}
 
void decompose(int at, int par){
	tot = 0;
	dfs0(at, at);
	int cen = get(at, at);
	vis[cen] = 1;
	if(par) anc[cen] = par;
	get_dis(cen, cen, 0);
	for(auto u : g[cen]){
		if(vis[u.first]) continue;
		decompose(u.first, cen);
	}
}
 
long long Query(int S, int X[], int T, int Y[]){
	++t;
	int cur, from;
	for(int i = 0; i < S; ++i){
		cur = X[i] + 1, from = X[i] + 1;
		for(int j = idx[from]; j >= 1; --j){
			if(lst[cur] == t) mn[cur] = min(mn[cur], pre[from][j]);
			else lst[cur] = t, 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;
		for(int j = idx[from]; j >= 1; --j){
			if(lst[cur] == t) ret = min(ret, mn[cur] + pre[from][j]);
			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]});
	}
	decompose(1, 0);
	for(int i = 1; i <= n; ++i) mn[i] = oo;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 147336 KB Output is correct
2 Correct 333 ms 147600 KB Output is correct
3 Correct 459 ms 147600 KB Output is correct
4 Correct 433 ms 147600 KB Output is correct
5 Correct 479 ms 147752 KB Output is correct
6 Correct 333 ms 147624 KB Output is correct
7 Correct 476 ms 147600 KB Output is correct
8 Correct 413 ms 147600 KB Output is correct
9 Correct 436 ms 147756 KB Output is correct
10 Correct 326 ms 147624 KB Output is correct
11 Correct 426 ms 147600 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 147336 KB Output is correct
2 Correct 3393 ms 172944 KB Output is correct
3 Correct 5406 ms 177380 KB Output is correct
4 Correct 1159 ms 171132 KB Output is correct
5 Execution timed out 6000 ms 200068 KB Execution timed out
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3709 ms 172944 KB Output is correct
2 Correct 3739 ms 172944 KB Output is correct
3 Correct 5479 ms 176400 KB Output is correct
4 Correct 5816 ms 176972 KB Output is correct
5 Correct 5253 ms 176836 KB Output is correct
6 Execution timed out 6000 ms 194288 KB Execution timed out
7 Halted 0 ms 0 KB -