oj.uz

Submission #310856

# Submission time Handle Problem Language Result Execution time Memory
310856 2020-10-08T08:50:45 Z vipghn2003 Factories (JOI14_factories) C++14
100 / 100
 2607 ms 230920 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
 
const int maxN = 5e5 + 7;
int n, level[maxN], st[maxN], ed[maxN], cnt = 0, now = 0, sz = 0, euler[2 * maxN], lg[2 * maxN], ft[maxN];
long long depth[maxN], ans;
pair <int, int> cur[4 * maxN], par[20][2 * maxN];
vector < pair <int, int> > edge[maxN];
 
void dfs(int u, int p){
	st[u] = ++cnt;
	euler[++now] = u;
	ft[u] = now;
	for(pair <int, int> to : edge[u]){
		int v = to.fi, w = to.se;
		if(v == p) continue;
		level[v] = level[u] + 1;
		depth[v] = depth[u] + w;
		dfs(v, u);
		euler[++now] = u;
	}
	ed[u] = cnt;
}
 
pair <int, int> get(int l, int r){
	int add = lg[r - l + 1];
	return min(par[add][l], par[add][r - (1 << add) + 1]);
}
 
int lca(int u, int v){
	if(ft[u] > ft[v]) swap(u, v);
	return get(ft[u], ft[v]).se;
}
 
bool cmp(pair <int, int> x, pair <int, int> y){
	return st[x.fi] < st[y.fi];
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++){
		A[i]++, B[i]++;
		edge[A[i]].pb(mp(B[i], D[i]));
		edge[B[i]].pb(mp(A[i], D[i]));
	}
	level[1] = 1;
	dfs(1, 1);
	for(int i = 1; i <= now; i++) par[0][i] = mp(level[euler[i]], euler[i]);
	for(int i = 2; i <= 2 * n; i++) lg[i] = lg[i >> 1] + 1;
	for(int i = 1; i < 20; i++){
		for(int j = 1; j + (1 << i) - 1 <= now; j++){
			par[i][j] = min(par[i - 1][j], par[i - 1][j + (1 << (i - 1))]);
		}
	}
	st[n + 1] = 1e9;
}
 
pair <long long, long long> solve(){
	int u = cur[cnt].fi;
	long long A = 1e18, B = 1e18;
	if(cur[cnt].se == 0) A = min(A, depth[u]);
	if(cur[cnt].se == 1) B = min(B, depth[u]);
	cnt++;
	if(cnt > sz) return mp(A, B);
	while(cur[cnt].fi == u){
		if(cur[cnt].se == 0) A = min(A, depth[u]);
		if(cur[cnt].se == 1) B = min(B, depth[u]);
		cnt++;
	}
	while(ed[u] >= st[cur[cnt].fi]){
		pair <long long, long long> tmp = solve();
		A = min(A, tmp.fi), B = min(B, tmp.se);
	}
	ans = min(ans, A + B - 2LL * depth[u]);
	return mp(A, B);
}
 
long long Query(int S, int X[], int T, int Y[]) {
	ans = 1e18;
	sz = 0;
	for(int i = 0; i < S; i++) cur[++sz] = mp(X[i] + 1, 0);
	for(int i = 0; i < T; i++) cur[++sz] = mp(Y[i] + 1, 1);
	sort(cur + 1, cur + 1 + sz, cmp);
	int sv = sz;
	for(int i = 1; i < sv; i++) cur[++sz] = mp(lca(cur[i].fi, cur[i + 1].fi), 2);
	cur[++sz] = mp(n + 1, 0);
	sort(cur + 1, cur + 1 + sz, cmp);
	//for(int i = 1; i <= sz; i++) cout << cur[i].fi << endl;
	cnt = 1;
	solve();
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12800 KB Output is correct
2 Correct 907 ms 29720 KB Output is correct
3 Correct 811 ms 29816 KB Output is correct
4 Correct 873 ms 29780 KB Output is correct
5 Correct 941 ms 29944 KB Output is correct
6 Correct 873 ms 29688 KB Output is correct
7 Correct 796 ms 29692 KB Output is correct
8 Correct 851 ms 29816 KB Output is correct
9 Correct 950 ms 29808 KB Output is correct
10 Correct 872 ms 29892 KB Output is correct
11 Correct 805 ms 29816 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12416 KB Output is correct
2 Correct 1402 ms 212588 KB Output is correct
3 Correct 1352 ms 212552 KB Output is correct
4 Correct 1162 ms 212572 KB Output is correct
5 Correct 1379 ms 229368 KB Output is correct
6 Correct 1438 ms 214228 KB Output is correct
7 Correct 974 ms 65272 KB Output is correct
8 Correct 872 ms 66152 KB Output is correct
9 Correct 876 ms 68036 KB Output is correct
10 Correct 936 ms 66424 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12800 KB Output is correct
2 Correct 907 ms 29720 KB Output is correct
3 Correct 811 ms 29816 KB Output is correct
4 Correct 873 ms 29780 KB Output is correct
5 Correct 941 ms 29944 KB Output is correct
6 Correct 873 ms 29688 KB Output is correct
7 Correct 796 ms 29692 KB Output is correct
8 Correct 851 ms 29816 KB Output is correct
9 Correct 950 ms 29808 KB Output is correct
10 Correct 872 ms 29892 KB Output is correct
11 Correct 805 ms 29816 KB Output is correct
12 Correct 10 ms 12416 KB Output is correct
13 Correct 1402 ms 212588 KB Output is correct
14 Correct 1352 ms 212552 KB Output is correct
15 Correct 1162 ms 212572 KB Output is correct
16 Correct 1379 ms 229368 KB Output is correct
17 Correct 1438 ms 214228 KB Output is correct
18 Correct 974 ms 65272 KB Output is correct
19 Correct 872 ms 66152 KB Output is correct
20 Correct 876 ms 68036 KB Output is correct
21 Correct 936 ms 66424 KB Output is correct
22 Correct 2607 ms 215332 KB Output is correct
23 Correct 2254 ms 217848 KB Output is correct
24 Correct 2500 ms 223740 KB Output is correct
25 Correct 2374 ms 220104 KB Output is correct
26 Correct 2130 ms 215460 KB Output is correct
27 Correct 2530 ms 230920 KB Output is correct
28 Correct 2074 ms 218812 KB Output is correct
29 Correct 2023 ms 215196 KB Output is correct
30 Correct 2048 ms 214716 KB Output is correct
31 Correct 2032 ms 215364 KB Output is correct
32 Correct 1497 ms 75716 KB Output is correct
33 Correct 1320 ms 73544 KB Output is correct
34 Correct 1281 ms 68856 KB Output is correct
35 Correct 1234 ms 68780 KB Output is correct
36 Correct 1170 ms 69112 KB Output is correct
37 Correct 1210 ms 69112 KB Output is correct