oj.uz

Submission #74085

# Submission time Handle Problem Language Result Execution time Memory
74085 2018-08-30T04:20:09 Z shoemakerjo Factories (JOI14_factories) C++14
15 / 100
 8000 ms 407780 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[19][maxn]; 
ll mycomp[19][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];
	}
}

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 < 19; 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 < 19; j++) {
			if (mycomp[j][val] == -1) continue;
			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 < 19; j++) {
			if (mycomp[j][val] != -1) {
				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 < 19; j++) {
			if (mycomp[j][val] != -1)
				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 97 ms 91000 KB Output is correct
2 Correct 561 ms 109240 KB Output is correct
3 Correct 598 ms 118788 KB Output is correct
4 Correct 576 ms 128384 KB Output is correct
5 Correct 606 ms 138152 KB Output is correct
6 Correct 472 ms 146796 KB Output is correct
7 Correct 588 ms 156880 KB Output is correct
8 Correct 573 ms 166196 KB Output is correct
9 Correct 630 ms 176004 KB Output is correct
10 Correct 493 ms 184364 KB Output is correct
11 Correct 593 ms 194340 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 194340 KB Output is correct
2 Correct 5518 ms 307436 KB Output is correct
3 Correct 7853 ms 343592 KB Output is correct
4 Correct 2937 ms 343592 KB Output is correct
5 Execution timed out 8025 ms 407780 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 91000 KB Output is correct
2 Correct 561 ms 109240 KB Output is correct
3 Correct 598 ms 118788 KB Output is correct
4 Correct 576 ms 128384 KB Output is correct
5 Correct 606 ms 138152 KB Output is correct
6 Correct 472 ms 146796 KB Output is correct
7 Correct 588 ms 156880 KB Output is correct
8 Correct 573 ms 166196 KB Output is correct
9 Correct 630 ms 176004 KB Output is correct
10 Correct 493 ms 184364 KB Output is correct
11 Correct 593 ms 194340 KB Output is correct
12 Correct 75 ms 194340 KB Output is correct
13 Correct 5518 ms 307436 KB Output is correct
14 Correct 7853 ms 343592 KB Output is correct
15 Correct 2937 ms 343592 KB Output is correct
16 Execution timed out 8025 ms 407780 KB Time limit exceeded
17 Halted 0 ms 0 KB -