oj.uz

Submission #74087

# Submission time Handle Problem Language Result Execution time Memory
74087 2018-08-30T04:27:26 Z shoemakerjo Factories (JOI14_factories) C++14
15 / 100
 7759 ms 208912 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pil pair<int, ll>

#define maxn 500010
int n;
vector<vector<pil>> adj(maxn);

//run a centroid decomposition


int subsize[maxn];
bool marked[maxn];
ll dr[18][maxn]; 
ll mycomp[18][maxn]; //which component i am in (specify by centroid is good)
ll curdist[maxn];
int cp[maxn];

ll inf = 1LL << 60;
ll curmin[maxn]; //for the queries
int cl;
int cc;

void dfs(int u, int p, bool op = false) {

	cp[u] = p;
	subsize[u] = 1;
	if (op) {
		// cout << u << " is in " << cc << " at level " << cl << endl;
		dr[cl][u] = curdist[u];
		mycomp[cl][u] = cc;
	}
	for (pil nx : adj[u]) {
		if (nx.first == p || marked[nx.first]) continue;
		curdist[nx.first] = curdist[u] + nx.second;

		dfs(nx.first, u, op);
		subsize[u] += subsize[nx.first];
	}
}

inline int getcentroid(int u, int csize) {
	curdist[u] = 0LL;
	dfs(u, -1);
	int cur = u;
	bool fin = false;
	while (!fin) {
		fin = true;
		for (pil nx : adj[cur]) {
			if (marked[nx.first] || nx.first == cp[cur]) continue;
			if (subsize[nx.first] > csize/2) {
				fin = false;
				cur = nx.first;
				break;
			}
		}	
	}
	return cur;

}

void go(int u, int csize, int level) {
	int cen = getcentroid(u, csize);
	curdist[cen] = 0LL;
	cc = cen;
	cl = level;
	dfs(cen, -1, true);
	marked[cen] = true;
	for (pil cur : adj[cen]) {
		if (!marked[cur.first])
			go(cur.first, subsize[cur.first], level+1);
	}

}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < 18; i++) {
		fill(mycomp[i], mycomp[i]+maxn, -1);
	}
	n = N;
	for (int i = 0; i < N-1; i++) {
		adj[A[i]].push_back(pil(B[i], D[i]));
		adj[B[i]].push_back(pil(A[i], D[i]));
	}
	fill(curmin, curmin+maxn, inf);
	go(0, n, 0);
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = inf;
	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 18; j++) {
			if (mycomp[j][val] == -1) break;
			curmin[mycomp[j][val]] = 
				min(curmin[mycomp[j][val]], dr[j][val]);
		}
	}

	for (int i = 0; i < T; i++) {
		int val = Y[i];
		for (int j = 0; j < 18; j++) {
			if (mycomp[j][val] == -1) break;
			
			ans = min(ans, 
				curmin[mycomp[j][val]] + dr[j][val]);
		}
	}

	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 18; j++) {
			if (mycomp[j][val] == -1) break;
			curmin[mycomp[j][val]] = inf;
		}
	}

  	return ans;
}

//COULD NOT SUBMIT AT TIME FIRST SOLVED

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 86904 KB Output is correct
2 Correct 469 ms 95536 KB Output is correct
3 Correct 517 ms 95664 KB Output is correct
4 Correct 514 ms 95664 KB Output is correct
5 Correct 530 ms 96144 KB Output is correct
6 Correct 368 ms 96144 KB Output is correct
7 Correct 500 ms 96144 KB Output is correct
8 Correct 527 ms 96144 KB Output is correct
9 Correct 541 ms 96232 KB Output is correct
10 Correct 365 ms 96232 KB Output is correct
11 Correct 480 ms 96232 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 96232 KB Output is correct
2 Correct 5012 ms 192756 KB Output is correct
3 Incorrect 7759 ms 208912 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 86904 KB Output is correct
2 Correct 469 ms 95536 KB Output is correct
3 Correct 517 ms 95664 KB Output is correct
4 Correct 514 ms 95664 KB Output is correct
5 Correct 530 ms 96144 KB Output is correct
6 Correct 368 ms 96144 KB Output is correct
7 Correct 500 ms 96144 KB Output is correct
8 Correct 527 ms 96144 KB Output is correct
9 Correct 541 ms 96232 KB Output is correct
10 Correct 365 ms 96232 KB Output is correct
11 Correct 480 ms 96232 KB Output is correct
12 Correct 64 ms 96232 KB Output is correct
13 Correct 5012 ms 192756 KB Output is correct
14 Incorrect 7759 ms 208912 KB Output isn't correct
15 Halted 0 ms 0 KB -