oj.uz

Submission #93478

# Submission time Handle Problem Language Result Execution time Memory
93478 2019-01-08T17:35:32 Z Dat160601 Factories (JOI14_factories) C++17
100 / 100
 2489 ms 254672 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 27 ms 12792 KB Output is correct
2 Correct 765 ms 22536 KB Output is correct
3 Correct 693 ms 22648 KB Output is correct
4 Correct 748 ms 22776 KB Output is correct
5 Correct 812 ms 22776 KB Output is correct
6 Correct 747 ms 22776 KB Output is correct
7 Correct 717 ms 22648 KB Output is correct
8 Correct 722 ms 22724 KB Output is correct
9 Correct 812 ms 22908 KB Output is correct
10 Correct 747 ms 22552 KB Output is correct
11 Correct 687 ms 22628 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12408 KB Output is correct
2 Correct 1385 ms 211560 KB Output is correct
3 Correct 1364 ms 212276 KB Output is correct
4 Correct 1073 ms 212264 KB Output is correct
5 Correct 1271 ms 229004 KB Output is correct
6 Correct 1145 ms 213852 KB Output is correct
7 Correct 782 ms 57548 KB Output is correct
8 Correct 705 ms 58584 KB Output is correct
9 Correct 650 ms 60520 KB Output is correct
10 Correct 735 ms 59072 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12792 KB Output is correct
2 Correct 765 ms 22536 KB Output is correct
3 Correct 693 ms 22648 KB Output is correct
4 Correct 748 ms 22776 KB Output is correct
5 Correct 812 ms 22776 KB Output is correct
6 Correct 747 ms 22776 KB Output is correct
7 Correct 717 ms 22648 KB Output is correct
8 Correct 722 ms 22724 KB Output is correct
9 Correct 812 ms 22908 KB Output is correct
10 Correct 747 ms 22552 KB Output is correct
11 Correct 687 ms 22628 KB Output is correct
12 Correct 14 ms 12408 KB Output is correct
13 Correct 1385 ms 211560 KB Output is correct
14 Correct 1364 ms 212276 KB Output is correct
15 Correct 1073 ms 212264 KB Output is correct
16 Correct 1271 ms 229004 KB Output is correct
17 Correct 1145 ms 213852 KB Output is correct
18 Correct 782 ms 57548 KB Output is correct
19 Correct 705 ms 58584 KB Output is correct
20 Correct 650 ms 60520 KB Output is correct
21 Correct 735 ms 59072 KB Output is correct
22 Correct 2340 ms 214404 KB Output is correct
23 Correct 2228 ms 241604 KB Output is correct
24 Correct 2489 ms 240136 KB Output is correct
25 Correct 2097 ms 243716 KB Output is correct
26 Correct 2094 ms 238692 KB Output is correct
27 Correct 2262 ms 254672 KB Output is correct
28 Correct 1879 ms 242600 KB Output is correct
29 Correct 1744 ms 238772 KB Output is correct
30 Correct 1943 ms 238324 KB Output is correct
31 Correct 1959 ms 238660 KB Output is correct
32 Correct 1375 ms 75960 KB Output is correct
33 Correct 1170 ms 73576 KB Output is correct
34 Correct 1095 ms 68828 KB Output is correct
35 Correct 1025 ms 68876 KB Output is correct
36 Correct 976 ms 69300 KB Output is correct
37 Correct 969 ms 69252 KB Output is correct