oj.uz

Submission #109308

# Submission time Handle Problem Language Result Execution time Memory
109308 2019-05-06T06:37:01 Z Diuven Factories (JOI14_factories) C++14
100 / 100
 5228 ms 143736 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, lint> pil;
typedef vector<int> Vint;
typedef vector<pil> Vpil;

const lint LNF = 2e18;
const int MAX = 5e5 + 10;
const int LG = 19;

int nu[MAX], ri[MAX], iv[MAX], dep[MAX], n;
int st[MAX][LG];
lint D[MAX];
vector<pil> G[MAX];

void dfs1(int v, int p, int cnt=0, lint sum=0){
	static int now = 0;
	nu[v] = ++now, ri[v] = nu[v], iv[nu[v]] = v;
	dep[v] = cnt, D[v] = sum;
	for(pil e:G[v]){
		int x; lint c; tie(x,c) = e;
		if(x==p) continue;
		st[x][0] = v;
		for(int i=1; i<LG; i++)
			st[x][i] = st[st[x][i-1]][i-1];
		dfs1(x,v,cnt+1,sum+c);
		ri[v] = ri[x];
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i=0; i<n-1; i++){
		int u = A[i], v = B[i], c = D[i];
		G[u].push_back({v,c});
		G[v].push_back({u,c});
	}
	dfs1(0,-1);
//	for(int i=0; i<n; i++) cout<<nu[i]<<' '<<ri[i]<<'\n';
}

int lca(int u, int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=LG-1; i>=0; i--)
		if(dep[u]-(1<<i)>=dep[v]) u = st[u][i];
	if(u==v) return u;
	for(int i=LG-1; i>=0; i--)
		if(st[u][i]!=st[v][i])
			u = st[u][i], v = st[v][i];
	return st[u][0];
}

int C[MAX];
lint A[MAX], B[MAX];
Vint V;

int idx;
lint dfs2(){
	int v = V[idx++];
	lint &a = A[v], &b = B[v], res = LNF;
	a = (C[v]==1 ? 0 : LNF);
	b = (C[v]==2 ? 0 : LNF);


	while(idx<int(V.size()) && V[idx]<=ri[iv[v]]){
		int x = V[idx];
		res = min(res, dfs2());
		a = min(a, D[iv[x]]-D[iv[v]] + A[x]);
		b = min(b, D[iv[x]]-D[iv[v]] + B[x]);
	}

	C[v] = 0, res = min(res, a+b);
	return res;
}


lint Query(int S, int X[], int T, int Y[]) {
	Vint P, Q; V.clear();
	for(int i=0; i<S; i++) P.push_back(nu[X[i]]);
	for(int i=0; i<T; i++) Q.push_back(nu[Y[i]]);

	for(int x:P) V.push_back(x), C[x] = 1;
	for(int x:Q) V.push_back(x), C[x] = 2;

	sort(V.begin(), V.end());

	for(int i=1, sz = int(V.size()); i<sz; i++)
		V.push_back(nu[lca(iv[V[i-1]], iv[V[i]])]);

	sort(V.begin(), V.end());
	V.resize(unique(V.begin(), V.end()) - V.begin());

	idx = 0;
	return dfs2();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12544 KB Output is correct
2 Correct 810 ms 21368 KB Output is correct
3 Correct 908 ms 21564 KB Output is correct
4 Correct 861 ms 21368 KB Output is correct
5 Correct 856 ms 21744 KB Output is correct
6 Correct 619 ms 21240 KB Output is correct
7 Correct 917 ms 21496 KB Output is correct
8 Correct 909 ms 21544 KB Output is correct
9 Correct 807 ms 21880 KB Output is correct
10 Correct 556 ms 21292 KB Output is correct
11 Correct 871 ms 21328 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12288 KB Output is correct
2 Correct 2235 ms 109548 KB Output is correct
3 Correct 3206 ms 113464 KB Output is correct
4 Correct 1876 ms 107168 KB Output is correct
5 Correct 3664 ms 143736 KB Output is correct
6 Correct 3529 ms 114732 KB Output is correct
7 Correct 3012 ms 40644 KB Output is correct
8 Correct 1771 ms 40480 KB Output is correct
9 Correct 3011 ms 45180 KB Output is correct
10 Correct 2518 ms 42152 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12544 KB Output is correct
2 Correct 810 ms 21368 KB Output is correct
3 Correct 908 ms 21564 KB Output is correct
4 Correct 861 ms 21368 KB Output is correct
5 Correct 856 ms 21744 KB Output is correct
6 Correct 619 ms 21240 KB Output is correct
7 Correct 917 ms 21496 KB Output is correct
8 Correct 909 ms 21544 KB Output is correct
9 Correct 807 ms 21880 KB Output is correct
10 Correct 556 ms 21292 KB Output is correct
11 Correct 871 ms 21328 KB Output is correct
12 Correct 15 ms 12288 KB Output is correct
13 Correct 2235 ms 109548 KB Output is correct
14 Correct 3206 ms 113464 KB Output is correct
15 Correct 1876 ms 107168 KB Output is correct
16 Correct 3664 ms 143736 KB Output is correct
17 Correct 3529 ms 114732 KB Output is correct
18 Correct 3012 ms 40644 KB Output is correct
19 Correct 1771 ms 40480 KB Output is correct
20 Correct 3011 ms 45180 KB Output is correct
21 Correct 2518 ms 42152 KB Output is correct
22 Correct 3192 ms 112388 KB Output is correct
23 Correct 3720 ms 114608 KB Output is correct
24 Correct 3520 ms 116476 KB Output is correct
25 Correct 4096 ms 120056 KB Output is correct
26 Correct 4670 ms 115320 KB Output is correct
27 Correct 4482 ms 141776 KB Output is correct
28 Correct 2530 ms 113172 KB Output is correct
29 Correct 5228 ms 114940 KB Output is correct
30 Correct 4932 ms 114232 KB Output is correct
31 Correct 5097 ms 114924 KB Output is correct
32 Correct 2229 ms 47572 KB Output is correct
33 Correct 1304 ms 42876 KB Output is correct
34 Correct 2290 ms 38548 KB Output is correct
35 Correct 2241 ms 38568 KB Output is correct
36 Correct 2411 ms 39536 KB Output is correct
37 Correct 2520 ms 39540 KB Output is correct