oj.uz

Submission #26546

# Submission time Handle Problem Language Result Execution time Memory
26546 2017-07-02T17:47:40 Z rubabredwan Factories (JOI14_factories) C++14
15 / 100
 6000 ms 233364 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;

set <pii> g[N];
int n;
int tot;
int sub[N];
int anc[N];
long long mn[N];
vector <long long> pre[N];
stack <int> rem;

inline void dfs0(int at, int par){
	++tot;
	sub[at] = 1;
	for(auto u : g[at]){
		if(u.first == par) continue;
		dfs0(u.first, at);
		sub[at] += sub[u.first];
	}
}

inline int get(int at, int par){
	for(auto u : g[at]){
		if(u.first == par) continue;
		if(sub[u.first] > tot / 2) return get(u.first, at);
	}
	return at;
}

inline void get_dis(int at, int par, long long dis){
	pre[at].push_back(dis);
	for(auto u : g[at]){
		if(u.first == par) continue;
		get_dis(u.first, at, dis + u.second);
	}
}

inline void decompose(int at, int par){
	tot = 0;
	dfs0(at, at);
	int cen = get(at, at);
	if(par) anc[cen] = par;
	get_dis(cen, cen, 0);
	for(auto u : g[cen]){
		g[u.first].erase({cen, u.second});
		decompose(u.first, cen);
	}
}

inline void update(int from){
	int cur = from;
	for(auto u : pre[from]){
		mn[cur] = min(mn[cur], u);
		rem.push(cur);
		cur = anc[cur];
	}
}

inline long long query(int from){
	int cur = from;
	long long ret = oo;
	for(auto u : pre[from]){
		ret = min(ret, mn[cur] + u);
		cur = anc[cur];
	}
	return ret;
}

void reset(){
	while(!rem.empty()){
		mn[rem.top()] = oo;
		rem.pop();
	}
}

long long Query(int S, int X[], int T, int Y[]){
	reset();
	for(int i = 0; i < S; ++i){
		update(X[i] + 1);
	}	
	long long ret = oo;
	for(int i = 0; i < T; ++i){
		ret = min(ret, query(Y[i] + 1));
	}
	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].insert({B[i] + 1, D[i]});
		g[B[i] + 1].insert({A[i] + 1, D[i]});
	}
	decompose(1, 0);
	for(int i = 1; i <= n; ++i) mn[i] = oo;
	for(int i = 1; i <= n; ++i){
		reverse(pre[i].begin(), pre[i].end());
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 67400 KB Output is correct
2 Correct 396 ms 68324 KB Output is correct
3 Correct 463 ms 68456 KB Output is correct
4 Correct 469 ms 68720 KB Output is correct
5 Correct 466 ms 68736 KB Output is correct
6 Correct 276 ms 68060 KB Output is correct
7 Correct 423 ms 68456 KB Output is correct
8 Correct 456 ms 68588 KB Output is correct
9 Correct 479 ms 68736 KB Output is correct
10 Correct 336 ms 68060 KB Output is correct
11 Correct 416 ms 68456 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67400 KB Output is correct
2 Correct 4513 ms 192668 KB Output is correct
3 Execution timed out 6000 ms 231316 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5413 ms 193980 KB Output is correct
2 Correct 5249 ms 196824 KB Output is correct
3 Execution timed out 6000 ms 233364 KB Execution timed out
4 Halted 0 ms 0 KB -