oj.uz

Submission #101062

# Submission time Handle Problem Language Result Execution time Memory
101062 2019-03-16T08:25:40 Z arman_ferdous Factories (JOI14_factories) C++17
100 / 100
 7813 ms 258952 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int N = 5e5+10;
const int M = N*2 + 100;
const ll INF = 1e18;
 
int n;
vector< pair<int,int> > g[N];
 
int eul[M], ptr, cheats[M];
int rmq[M][20], val[M][20], pos[N];
ll lev[N], dep[N];
void lcadfs(int u, int f, ll l, int d) {
	lev[u] = l;
	dep[u] = d;
	pos[u] = ptr;
	eul[ptr++] = u;
	for(auto it : g[u]) if(it.first != f) {
		lcadfs(it.first, u, l + it.second, d + 1);
		eul[ptr++] = u;
	}
}
int lca(int u, int v) {
	if(pos[u] > pos[v]) swap(u,v);
	int k = 31 - __builtin_clz(pos[v] - pos[u]);
	if(rmq[pos[u]][k] < rmq[pos[v] - (1<<k) + 1][k]) return val[pos[u]][k];
	return val[pos[v] - (1<<k) + 1][k];
}
ll dist(int u, int v) {
	return lev[u] + lev[v] - 2ll*lev[lca(u,v)];
}
 
int Deleted[N], sub[N], head[N];
int subdfs(int u, int f) {
	sub[u] = 1;
	for(auto it : g[u]) if(it.first != f && !Deleted[it.first])
		sub[u] += subdfs(it.first, u);
	return sub[u];
}
int get_centroid(int u, int f, int lim) {
	for(auto it : g[u]) if(it.first != f && !Deleted[it.first])
		if(sub[it.first] > lim) return get_centroid(it.first, u, lim);
	return u;
}
void decompose(int s, int dad) {
	subdfs(s,-1);
	int u = get_centroid(s, -1, sub[s]/2);
	head[u] = dad;
	Deleted[u] = 1;
	for(auto it : g[u]) if(!Deleted[it.first])
		decompose(it.first, u);
}
 
ll mnDist[N]; int deNode[N];
void Init(int n_, int A[], int B[], int D[]) {
	n = n_;
	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]});
	}
	lcadfs(0,-1,0,0);
 
 	for(int i = 1; i <= ptr; i++) cheats[i] = 31 - __builtin_clz(i);
	for(int i = 0; i < ptr; i++) {
		rmq[i][0] = dep[eul[i]];
		val[i][0] = eul[i];
	}
	for(int j = 1; j < 20; j++) {
		for(int i = 0; i + (1<<j) - 1 < ptr; i++) {
			int x = i+(1<<(j-1));
			if(rmq[i][j-1] < rmq[x][j-1]) {
				rmq[i][j] = rmq[i][j-1];
				val[i][j] = val[i][j-1];
			} else {
				rmq[i][j] = rmq[x][j-1];
				val[i][j] = val[x][j-1];
			}
		}
	}
	decompose(0,-1);
	for(int i = 0; i < n; i++)
		mnDist[i] = INF, deNode[i] = -1;
}
 
void add(int u) {
	for(int p = u; p + 1; p = head[p]) {
		ll d = dist(u, p);
		if(d < mnDist[p]) mnDist[p] = d, deNode[p] = u;
	}
}
void remove(int u) {
	for(int p = u; p + 1 && mnDist[p] != INF; p = head[p])
		mnDist[p] = INF, deNode[p] = -1;
}
ll get(int u) {
	ll ret = INF;
	for(int p = u; p + 1; p = head[p]) if(deNode[p] + 1)
		ret = min(ret, dist(u, deNode[p]));
	return ret;
}
 
ll Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i++) add(X[i]);
	ll ret = INF;
	for(int i = 0; i < T; i++)
		ret = min(ret, get(Y[i]));
	for(int i = 0; i < S; i++) remove(X[i]);
  	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12672 KB Output is correct
2 Correct 581 ms 22404 KB Output is correct
3 Correct 751 ms 22540 KB Output is correct
4 Correct 631 ms 22520 KB Output is correct
5 Correct 744 ms 22520 KB Output is correct
6 Correct 317 ms 22312 KB Output is correct
7 Correct 731 ms 22520 KB Output is correct
8 Correct 765 ms 22392 KB Output is correct
9 Correct 726 ms 22628 KB Output is correct
10 Correct 356 ms 22428 KB Output is correct
11 Correct 761 ms 22392 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12544 KB Output is correct
2 Correct 3515 ms 229672 KB Output is correct
3 Correct 4842 ms 231300 KB Output is correct
4 Correct 1921 ms 230492 KB Output is correct
5 Correct 5994 ms 253712 KB Output is correct
6 Correct 5135 ms 232668 KB Output is correct
7 Correct 2657 ms 64132 KB Output is correct
8 Correct 777 ms 64716 KB Output is correct
9 Correct 2373 ms 67600 KB Output is correct
10 Correct 2437 ms 65520 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12672 KB Output is correct
2 Correct 581 ms 22404 KB Output is correct
3 Correct 751 ms 22540 KB Output is correct
4 Correct 631 ms 22520 KB Output is correct
5 Correct 744 ms 22520 KB Output is correct
6 Correct 317 ms 22312 KB Output is correct
7 Correct 731 ms 22520 KB Output is correct
8 Correct 765 ms 22392 KB Output is correct
9 Correct 726 ms 22628 KB Output is correct
10 Correct 356 ms 22428 KB Output is correct
11 Correct 761 ms 22392 KB Output is correct
12 Correct 14 ms 12544 KB Output is correct
13 Correct 3515 ms 229672 KB Output is correct
14 Correct 4842 ms 231300 KB Output is correct
15 Correct 1921 ms 230492 KB Output is correct
16 Correct 5994 ms 253712 KB Output is correct
17 Correct 5135 ms 232668 KB Output is correct
18 Correct 2657 ms 64132 KB Output is correct
19 Correct 777 ms 64716 KB Output is correct
20 Correct 2373 ms 67600 KB Output is correct
21 Correct 2437 ms 65520 KB Output is correct
22 Correct 5421 ms 231420 KB Output is correct
23 Correct 4367 ms 233592 KB Output is correct
24 Correct 6617 ms 233088 KB Output is correct
25 Correct 6925 ms 236624 KB Output is correct
26 Correct 7404 ms 233252 KB Output is correct
27 Correct 7813 ms 251976 KB Output is correct
28 Correct 2267 ms 258952 KB Output is correct
29 Correct 7245 ms 257196 KB Output is correct
30 Correct 6967 ms 256656 KB Output is correct
31 Correct 6930 ms 257384 KB Output is correct
32 Correct 2920 ms 82580 KB Output is correct
33 Correct 836 ms 79344 KB Output is correct
34 Correct 2110 ms 76008 KB Output is correct
35 Correct 2081 ms 76004 KB Output is correct
36 Correct 2591 ms 76288 KB Output is correct
37 Correct 2890 ms 76392 KB Output is correct