oj.uz

Submission #44260

# Submission time Handle Problem Language Result Execution time Memory
44260 2018-03-31T03:21:11 Z szawinis Factories (JOI14_factories) C++17
100 / 100
 5952 ms 460600 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e17;
 
int n;
vector<int> sz, nxt;
vector<vector<pair<int,int> > > g;
vector<vector<ll> > d;
vector<bool> block;
vector<ll> mn;
 
void init_dfs(int u, int par, ll curr_dist = 0) {
	d[u].push_back(curr_dist);
	sz[u] = 1;
	for(auto p: g[u]) {
		int v, w; tie(v, w) = p;
		if(block[v] || v == par) continue;
		init_dfs(v, u, curr_dist + w);
		sz[u] += sz[v];
	}
}
 
void calc(int src, int par) {
	int cen = src;
	while(true) {
		bool found = false;
		for(auto p: g[cen]) if(sz[p.first] < sz[cen] && sz[p.first] << 1 >= sz[src]) {
			cen = p.first;
			found = true;
			break;
		}
		if(!found) break;
	}
	block[cen] = true;
	nxt[cen] = par;
	init_dfs(cen, -1);
	// cout << cen << ' ' << nxt[cen] << endl;
	for(auto p: g[cen]) if(!block[p.first]) calc(p.first, cen);
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	g.resize(n), sz.resize(n), nxt.resize(n), d.resize(n), block.resize(n);
	mn.assign(n, INF);
	for(int i = 0; i < n-1; i++) {
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	init_dfs(0, -1);
	calc(0, -1);
}
 
ll Query(int S, int X[], int T, int Y[]) {
	ll ret = INF;
	for(int i = 0; i < S; i++) for(int j = d[X[i]].size()-1, v = X[i]; j > 0; j--, v = nxt[v])
		mn[v] = min(d[X[i]][j], mn[v]);
	for(int i = 0; i < T; i++) for(int j = d[Y[i]].size()-1, v = Y[i]; j > 0; j--, v = nxt[v])
		ret = min(mn[v] + d[Y[i]][j], ret);
	for(int i = 0; i < S; i++) for(int j = d[X[i]].size()-1, v = X[i]; j > 0; j--, v = nxt[v])
		mn[v] = INF;
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 760 KB Output is correct
2 Correct 397 ms 9972 KB Output is correct
3 Correct 380 ms 10204 KB Output is correct
4 Correct 378 ms 10272 KB Output is correct
5 Correct 399 ms 10564 KB Output is correct
6 Correct 325 ms 10564 KB Output is correct
7 Correct 449 ms 10564 KB Output is correct
8 Correct 374 ms 10564 KB Output is correct
9 Correct 394 ms 10756 KB Output is correct
10 Correct 301 ms 10756 KB Output is correct
11 Correct 395 ms 10756 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10756 KB Output is correct
2 Correct 2852 ms 133004 KB Output is correct
3 Correct 4043 ms 182580 KB Output is correct
4 Correct 1371 ms 182580 KB Output is correct
5 Correct 5318 ms 263048 KB Output is correct
6 Correct 4238 ms 263048 KB Output is correct
7 Correct 1206 ms 263048 KB Output is correct
8 Correct 561 ms 263048 KB Output is correct
9 Correct 1465 ms 263048 KB Output is correct
10 Correct 1286 ms 263048 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3499 ms 263048 KB Output is correct
2 Correct 3515 ms 263048 KB Output is correct
3 Correct 5033 ms 295760 KB Output is correct
4 Correct 5094 ms 324120 KB Output is correct
5 Correct 5227 ms 344556 KB Output is correct
6 Correct 5952 ms 404696 KB Output is correct
7 Correct 1756 ms 404696 KB Output is correct
8 Correct 4996 ms 414612 KB Output is correct
9 Correct 5234 ms 437200 KB Output is correct
10 Correct 5156 ms 460600 KB Output is correct
11 Correct 1528 ms 460600 KB Output is correct
12 Correct 684 ms 460600 KB Output is correct
13 Correct 995 ms 460600 KB Output is correct
14 Correct 1051 ms 460600 KB Output is correct
15 Correct 1250 ms 460600 KB Output is correct
16 Correct 1280 ms 460600 KB Output is correct