oj.uz

Submission #472972

# Submission time Handle Problem Language Result Execution time Memory
472972 2021-09-14T16:26:57 Z ngpin04 Factories (JOI14_factories) C++14
100 / 100
 6417 ms 172824 KB 
//#include "grader.cpp"
//#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int Nmax = 5e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = 3.14159265359;

vector <pair <int, int>> adj[Nmax];

long long d[Nmax];
long long mind[Nmax];

int t[2 * Nmax][20];
int lg2[2 * Nmax];
int tin[Nmax];
int par[Nmax];
int sz[Nmax];
int h[Nmax];
int timer;

bool bk[Nmax];

int getmin(int u, int v) {
	return (h[u] < h[v]) ? u : v;
}

void dfs(int u, int p = -1) {
	t[++timer][0] = u;
	tin[u] = timer;
	for (pair <int, int> to : adj[u]) {
		int v = to.fi;
		int w = to.se;
		if (v == p)
			continue;
		h[v] = h[u] + 1;
		d[v] = d[u] + w;
		dfs(v, u);
		t[++timer][0] = u;
	}
}

void build() {
	for (int j = 1; j < 20; j++)
	for (int i = 1; i + (1 << j) - 1 <= timer; i++)
		t[i][j] = getmin(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
}

long long dis(int u, int v) {
	int l = tin[u];
	int r = tin[v];
	if (l > r)
		swap(l, r);
	int lg = lg2[r - l + 1];
	int p = getmin(t[l][lg], t[r - (1 << lg) + 1][lg]);
	// cerr << u << " " << v << " " << p << "\n";
	return d[u] + d[v] - (d[p] << 1);
}

int calc(int u, int p = -1) {
	sz[u] = 1;
	for (pair <int, int> to : adj[u]) {
		int v = to.fi;
		if (v == p || bk[v])
			continue;
		sz[u] += calc(v, u);
	} 
	return sz[u];
}

int getcen(int u, int S, int p = -1) {
	for (pair <int, int> to : adj[u]) {
		int v = to.fi;
		if (v == p || bk[v] || (sz[v] << 1) <= S)
			continue;
		return getcen(v, S, u);
	}
	return u;
}

int centroid(int u) {
	int r = getcen(u, calc(u));

	bk[r] = true;
	for (pair <int, int> to : adj[r]) {	
		int v = to.fi;
		if (bk[v])
			continue;
		par[centroid(v)] = r;
	}
	return r;
}

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 0; i < n - 1; i++) {
		adj[a[i]].push_back(mp(b[i], d[i]));
		adj[b[i]].push_back(mp(a[i], d[i]));
	}

	for (int i = 0; i < 2 * Nmax; i++)
		lg2[i] = log2(i);

	dfs(0);
	build();
	par[centroid(0)] = -1;
	for (int i = 0; i < n; i++)
		mind[i] = ooo;
}

void reset(int u) {
	for (int v = u; v != -1; v = par[v])
		mind[v] = ooo;
}

void update(int u) {
	for (int v = u; v != -1; v = par[v])
		mini(mind[v], dis(u, v));
} 

long long getans(int u) {
	long long res = ooo;
	for (int v = u; v != -1; v = par[v])
		mini(res, mind[v] + dis(u, v));
	return res;
}

long long Query(int s, int x[], int t, int y[]) {
	for (int i = 0; i < s; i++)
		update(x[i]);

	long long res = ooo;
	for (int i = 0; i < t; i++) 
		mini(res, getans(y[i]));

	for (int i = 0; i < s; i++)
		reset(x[i]);
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16324 KB Output is correct
2 Correct 528 ms 25224 KB Output is correct
3 Correct 705 ms 25152 KB Output is correct
4 Correct 693 ms 25320 KB Output is correct
5 Correct 745 ms 25540 KB Output is correct
6 Correct 305 ms 25156 KB Output is correct
7 Correct 704 ms 25248 KB Output is correct
8 Correct 723 ms 25288 KB Output is correct
9 Correct 748 ms 25568 KB Output is correct
10 Correct 316 ms 25156 KB Output is correct
11 Correct 714 ms 25348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16176 KB Output is correct
2 Correct 2661 ms 141876 KB Output is correct
3 Correct 3588 ms 144216 KB Output is correct
4 Correct 1088 ms 142692 KB Output is correct
5 Correct 4705 ms 172824 KB Output is correct
6 Correct 3924 ms 145744 KB Output is correct
7 Correct 2143 ms 49816 KB Output is correct
8 Correct 648 ms 50208 KB Output is correct
9 Correct 2363 ms 53804 KB Output is correct
10 Correct 2179 ms 50896 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16324 KB Output is correct
2 Correct 528 ms 25224 KB Output is correct
3 Correct 705 ms 25152 KB Output is correct
4 Correct 693 ms 25320 KB Output is correct
5 Correct 745 ms 25540 KB Output is correct
6 Correct 305 ms 25156 KB Output is correct
7 Correct 704 ms 25248 KB Output is correct
8 Correct 723 ms 25288 KB Output is correct
9 Correct 748 ms 25568 KB Output is correct
10 Correct 316 ms 25156 KB Output is correct
11 Correct 714 ms 25348 KB Output is correct
12 Correct 24 ms 16176 KB Output is correct
13 Correct 2661 ms 141876 KB Output is correct
14 Correct 3588 ms 144216 KB Output is correct
15 Correct 1088 ms 142692 KB Output is correct
16 Correct 4705 ms 172824 KB Output is correct
17 Correct 3924 ms 145744 KB Output is correct
18 Correct 2143 ms 49816 KB Output is correct
19 Correct 648 ms 50208 KB Output is correct
20 Correct 2363 ms 53804 KB Output is correct
21 Correct 2179 ms 50896 KB Output is correct
22 Correct 3965 ms 143380 KB Output is correct
23 Correct 3921 ms 145640 KB Output is correct
24 Correct 5784 ms 146008 KB Output is correct
25 Correct 5533 ms 149600 KB Output is correct
26 Correct 5481 ms 146200 KB Output is correct
27 Correct 6417 ms 169440 KB Output is correct
28 Correct 1475 ms 171180 KB Output is correct
29 Correct 5507 ms 170072 KB Output is correct
30 Correct 5505 ms 169520 KB Output is correct
31 Correct 5700 ms 170220 KB Output is correct
32 Correct 2284 ms 68952 KB Output is correct
33 Correct 716 ms 64696 KB Output is correct
34 Correct 1592 ms 61248 KB Output is correct
35 Correct 1669 ms 61248 KB Output is correct
36 Correct 2055 ms 62100 KB Output is correct
37 Correct 2121 ms 61896 KB Output is correct