oj.uz

Submission #306340

# Submission time Handle Problem Language Result Execution time Memory
306340 2020-09-25T09:13:50 Z syy Factories (JOI14_factories) C++17
100 / 100
 4392 ms 163756 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
#define f first
#define s second

vector <pi> adjlist[500005];
int sub[500005], lvl[500005], p[500005];
ll dist[500005][19], ans[500005];
stack <int> st;
ll INF = 1e18;

int subtrsz(int x, int par, int l) {
	sub[x] = 1;
	//subtree size is 1
	for (auto it:adjlist[x]) {
		if (lvl[it.f] != -1) continue;
		// already added to centroid tree
		if (it.f == par) continue;
		if (l) dist[it.f][l-1] = dist[x][l-1] + it.s;
		sub[x] += subtrsz(it.f, x, l);
	}
	return sub[x];
}

int findcent(int x, int par, int n) {
	//n is size of subtree
	for (auto it:adjlist[x]) {
		if (lvl[it.f] != -1) continue;
		// Already added to centroid tree
		if (it.f != par and sub[it.f] > n/2) {
			return findcent(it.f, x, n);
		}
	}
	return x; // No subtree has size > n/2
	// so you are the centroid
}
//building from node x, with parent par, level l
void build(int x, int par, int l) {
	int n = subtrsz(x, par, l);
	int cent = findcent(x, par, n);
	// find centroid with the subtree size
	if (par == -1) par = cent; //par of root is itself
	p[cent] = par; //set parent of centroid
	// to be the previous centroid
	lvl[cent] = l;
	for (auto it:adjlist[cent]) {
		if (lvl[it.f] != -1) continue;
		// already added to centroid tree
		dist[it.f][l] = it.s; 
		// distance from this node to the centroid at level l
		build(it.f, cent, l+1);
	}
}

void update(int x) {
	int l = lvl[x];
	int y = x;
	while (l != -1) {
		ans[y] = min(ans[y], dist[x][l]);
		//ans[y] = min distance from any node
		//of Factory A to y.
		//here we process by x
		st.push(y);
		y = p[y];
		l--;
	}
}

ll findans(int x) {
	ll ret = INF;
	int l = lvl[x];
	int y = x;
	while (l != -1) {
		ret = min(ret, ans[y] + dist[x][l]);
		//for every centroid, add dist from
		//best Factory A node to querying Factory B node
		//then min with running answer
		y = p[y];
		l--;
	}
	return ret;
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N-1; i++) {
		adjlist[A[i]].push_back(pi(B[i], D[i]));
		adjlist[B[i]].push_back(pi(A[i], D[i]));
	}
	memset(lvl, -1, sizeof lvl);
	build(0, -1, 0); //build centroid tree
	for (int i = 0; i < N; i++) ans[i] = INF;
	//for (int i=0;i<N;++i)cout<<p[i]<<' '<<lvl[i]<<' '<<dist[i][0]<<'\n';cout<<'\n';
}

long long Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) update(X[i]);
	//find min dist from every node to Factory A nodes
	ll ret = INF;
	for (int i = 0; i < T; i++) ret = min(ret, findans(Y[i]));
	//find min dist from every node to Factory B nodes
	while (st.size()) {
		ans[st.top()] = INF;
		st.pop();
	}
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14592 KB Output is correct
2 Correct 383 ms 32632 KB Output is correct
3 Correct 409 ms 32632 KB Output is correct
4 Correct 416 ms 32760 KB Output is correct
5 Correct 439 ms 32888 KB Output is correct
6 Correct 315 ms 32760 KB Output is correct
7 Correct 407 ms 32632 KB Output is correct
8 Correct 427 ms 32632 KB Output is correct
9 Correct 440 ms 32888 KB Output is correct
10 Correct 319 ms 32632 KB Output is correct
11 Correct 415 ms 32632 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14336 KB Output is correct
2 Correct 1896 ms 146388 KB Output is correct
3 Correct 2569 ms 130552 KB Output is correct
4 Correct 890 ms 128736 KB Output is correct
5 Correct 3495 ms 158988 KB Output is correct
6 Correct 2654 ms 131960 KB Output is correct
7 Correct 1024 ms 55804 KB Output is correct
8 Correct 564 ms 59880 KB Output is correct
9 Correct 1193 ms 63608 KB Output is correct
10 Correct 1036 ms 60664 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14592 KB Output is correct
2 Correct 383 ms 32632 KB Output is correct
3 Correct 409 ms 32632 KB Output is correct
4 Correct 416 ms 32760 KB Output is correct
5 Correct 439 ms 32888 KB Output is correct
6 Correct 315 ms 32760 KB Output is correct
7 Correct 407 ms 32632 KB Output is correct
8 Correct 427 ms 32632 KB Output is correct
9 Correct 440 ms 32888 KB Output is correct
10 Correct 319 ms 32632 KB Output is correct
11 Correct 415 ms 32632 KB Output is correct
12 Correct 12 ms 14336 KB Output is correct
13 Correct 1896 ms 146388 KB Output is correct
14 Correct 2569 ms 130552 KB Output is correct
15 Correct 890 ms 128736 KB Output is correct
16 Correct 3495 ms 158988 KB Output is correct
17 Correct 2654 ms 131960 KB Output is correct
18 Correct 1024 ms 55804 KB Output is correct
19 Correct 564 ms 59880 KB Output is correct
20 Correct 1193 ms 63608 KB Output is correct
21 Correct 1036 ms 60664 KB Output is correct
22 Correct 2265 ms 137980 KB Output is correct
23 Correct 2355 ms 154340 KB Output is correct
24 Correct 3334 ms 140304 KB Output is correct
25 Correct 3427 ms 143820 KB Output is correct
26 Correct 3515 ms 138608 KB Output is correct
27 Correct 4392 ms 163756 KB Output is correct
28 Correct 1146 ms 139228 KB Output is correct
29 Correct 3339 ms 138220 KB Output is correct
30 Correct 3396 ms 137592 KB Output is correct
31 Correct 3345 ms 138140 KB Output is correct
32 Correct 1206 ms 66564 KB Output is correct
33 Correct 566 ms 60648 KB Output is correct
34 Correct 836 ms 56952 KB Output is correct
35 Correct 812 ms 57084 KB Output is correct
36 Correct 991 ms 57592 KB Output is correct
37 Correct 1000 ms 57720 KB Output is correct