oj.uz

Submission #308747

# Submission time Handle Problem Language Result Execution time Memory
308747 2020-10-01T20:20:17 Z pit4h Factories (JOI14_factories) C++14
100 / 100
 6925 ms 229804 KB 
#include "factories.h"
#include<bits/stdc++.h>
/*#ifndef LOCAL
#define cerr if(0)cerr
#endif
*/
#define st first
#define nd second
using namespace std;
using ll = long long;
const int MAXN = 5e5+1;
const ll INF = 1e16+1;
vector<pair<int, int>> g[MAXN];
ll h[MAXN];
vector<int> euler, positions[MAXN];
int l[MAXN], r[MAXN];
void dfs(int x, int p) {
	euler.push_back(x);
	l[x] = r[x] = euler.size()-1;
	for(auto i: g[x]) {
		if(i.st != p) {
			h[i.st] = h[x] + i.nd;
			dfs(i.st, x);
			euler.push_back(x);
			r[x] = euler.size()-1;
		}
	}
}
struct Segtree {
	vector<pair<ll, int>> tree;
	int base;
	vector<int> history;
	void init(int sz) {
		base=1;
		while(base<sz) base *= 2;
		tree.resize(2*base+1, {INF, -1});
	}
	void ins(int pos, pair<ll, int> val) {
		history.push_back(pos);
		pos += base;
		while(pos) {
			tree[pos] = min(tree[pos], val);	
			pos /= 2;
		}
	}
	void del(int pos) {
		pos += base;
		while(pos) {
			tree[pos] = {INF, -1};
			pos /= 2;
		}
	}
	void clr() {
		for(int i: history) del(i);
		history.clear();
	}
	int query(int L, int R) {
		L += base;
		R += base;
		pair<ll, int> res = min(tree[L], tree[R]);
		while(L/2 != R/2) {
			if(L%2==0) {
				res = min(res, tree[L+1]);
			}
			if(R%2==1) {
				res = min(res, tree[R-1]);
			}
			L /= 2;
			R /= 2;
		}
		return res.nd;
	}
};
Segtree Tree, Ts, Tt;
int LCA(int x, int y) {
	return Tree.query(min(l[x], l[y]), max(r[x], r[y]));
}
void Init(int N, int A[], int B[], int D[]) {
	for(int i=0; i<N-1; ++i) {
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, 0);
	Tree.init(euler.size());
	for(int i=0; i<(int)euler.size(); ++i) {
		positions[euler[i]].push_back(i);
		Tree.ins(i, {h[euler[i]], euler[i]});
	}
	Ts.init(euler.size());
	Tt.init(euler.size());
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<pair<int, int>> vec;
	for(int i=0; i<S; ++i) {
		vec.push_back({l[X[i]], X[i]});
		for(int j: positions[X[i]]) {
			Ts.ins(j, {h[X[i]], X[i]});
		}
	}
	for(int i=0; i<T; ++i) {
		vec.push_back({l[Y[i]], Y[i]});
		for(int j: positions[Y[i]]) {
			Tt.ins(j, {h[Y[i]], Y[i]});
		}
	}
	sort(vec.begin(), vec.end());
	ll ans = INF;
	vector<int> nodes;
	for(int i=1; i<(int)vec.size(); ++i) {
		int lca = LCA(vec[i-1].nd, vec[i].nd);
		nodes.push_back(lca);
	}
	for(int lca: nodes) {
		int it1 = Ts.query(l[lca], r[lca]), it2 = Tt.query(l[lca], r[lca]);
		if(it1 == -1 || it2 == -1) continue;
		ans = min(ans, h[it1] + h[it2] - 2*h[lca]);
	}
	Ts.clr();
	Tt.clr();
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24440 KB Output is correct
2 Correct 1386 ms 43640 KB Output is correct
3 Correct 1673 ms 43640 KB Output is correct
4 Correct 1519 ms 43724 KB Output is correct
5 Correct 1520 ms 43800 KB Output is correct
6 Correct 1166 ms 43720 KB Output is correct
7 Correct 1705 ms 43752 KB Output is correct
8 Correct 1509 ms 43764 KB Output is correct
9 Correct 1512 ms 43768 KB Output is correct
10 Correct 1137 ms 43760 KB Output is correct
11 Correct 1691 ms 43648 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24064 KB Output is correct
2 Correct 3378 ms 204640 KB Output is correct
3 Correct 3862 ms 186848 KB Output is correct
4 Correct 2858 ms 193084 KB Output is correct
5 Correct 4046 ms 204384 KB Output is correct
6 Correct 4054 ms 188344 KB Output is correct
7 Correct 4506 ms 83260 KB Output is correct
8 Correct 2987 ms 86024 KB Output is correct
9 Correct 4342 ms 86280 KB Output is correct
10 Correct 4360 ms 84724 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24440 KB Output is correct
2 Correct 1386 ms 43640 KB Output is correct
3 Correct 1673 ms 43640 KB Output is correct
4 Correct 1519 ms 43724 KB Output is correct
5 Correct 1520 ms 43800 KB Output is correct
6 Correct 1166 ms 43720 KB Output is correct
7 Correct 1705 ms 43752 KB Output is correct
8 Correct 1509 ms 43764 KB Output is correct
9 Correct 1512 ms 43768 KB Output is correct
10 Correct 1137 ms 43760 KB Output is correct
11 Correct 1691 ms 43648 KB Output is correct
12 Correct 20 ms 24064 KB Output is correct
13 Correct 3378 ms 204640 KB Output is correct
14 Correct 3862 ms 186848 KB Output is correct
15 Correct 2858 ms 193084 KB Output is correct
16 Correct 4046 ms 204384 KB Output is correct
17 Correct 4054 ms 188344 KB Output is correct
18 Correct 4506 ms 83260 KB Output is correct
19 Correct 2987 ms 86024 KB Output is correct
20 Correct 4342 ms 86280 KB Output is correct
21 Correct 4360 ms 84724 KB Output is correct
22 Correct 4699 ms 197092 KB Output is correct
23 Correct 5047 ms 217328 KB Output is correct
24 Correct 5344 ms 196580 KB Output is correct
25 Correct 5646 ms 219032 KB Output is correct
26 Correct 6839 ms 212400 KB Output is correct
27 Correct 5983 ms 229804 KB Output is correct
28 Correct 3868 ms 222084 KB Output is correct
29 Correct 6724 ms 211940 KB Output is correct
30 Correct 6925 ms 211568 KB Output is correct
31 Correct 6745 ms 212096 KB Output is correct
32 Correct 3359 ms 89748 KB Output is correct
33 Correct 2465 ms 88536 KB Output is correct
34 Correct 3825 ms 81376 KB Output is correct
35 Correct 3829 ms 81452 KB Output is correct
36 Correct 4327 ms 81784 KB Output is correct
37 Correct 4313 ms 81736 KB Output is correct