oj.uz

Submission #111120

# Submission time Handle Problem Language Result Execution time Memory
111120 2019-05-13T17:09:02 Z Plasmatic Factories (JOI14_factories) C++11
100 / 100
 7481 ms 237452 KB 
//============================================================================
// Name        : joi14p1.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// Scan and Debug
void scan(){}
template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
int di_; string dnms_, co_ = ",";
void debug_(){cout<<endl;}
template<typename F, typename... R> void debug_(F f, R... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
#define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)

const int MAX = 500001;

struct ed {
	int v, w;
};

vector<ed> matrix[MAX];
const ll INF = 0x3f3f3f3f3f3f3f3f;
int N,
	sz[MAX], par[MAX], lv[MAX];
bool blocked[MAX];
ll bestFor[MAX];
vector<int> back;
vector<ll> dis[MAX];

int gsz(int cur, int par) {
	sz[cur] = 1;
	for (ed adj : matrix[cur])
		if ((adj.v ^ par) && !blocked[adj.v])
			sz[cur] += gsz(adj.v, cur);
	return sz[cur];
}

int gcentroid(int cur, int par, int half) {
	for (ed adj : matrix[cur])
		if ((adj.v ^ par) && !blocked[adj.v] && sz[adj.v] > half)
			return gcentroid(adj.v, cur, half);
	return cur;
}

void dfs(int cur, int par=-1, ll __dis=0) {
	dis[cur].push_back(__dis);
	for (ed adj : matrix[cur])
		if ((adj.v ^ par) && !blocked[adj.v])
			dfs(adj.v, cur, __dis + adj.w);
}

int decomp(int cur=0, int __par=-1, int __lv=0) {
	gsz(cur, __par);
	if (sz[cur] == 1) {// If size is one, centroid is self
		lv[cur] = __lv;
		return cur;
	}

	int centroid = gcentroid(cur, __par, sz[cur] >> 1);
	lv[centroid] = __lv;
	blocked[centroid] = true;
	dfs(centroid);

	for (ed adj : matrix[centroid])
		if (!blocked[adj.v])
			par[decomp(adj.v, centroid, __lv + 1)] = centroid;

	return centroid;
}

// Grader Functions
void Init(int N_, int A[], int B[], int D[]) {
	N = N_;
	for (int i = 0; i < N - 1; i++) {
		matrix[A[i]].push_back({B[i], D[i]});
		matrix[B[i]].push_back({A[i], D[i]});
	}

	// Init Centroid Tree
	par[decomp()] = -1;
	memset(bestFor, 0x3f, sizeof bestFor);
}

long long Query(int S, int X[], int T, int Y[]) {
	ll best = INF;

	for (int i = 0; i < T; i++) {
		for (int cur = Y[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--) {
			bestFor[cur] = min(bestFor[cur], dis[Y[i]][clv]), assert(cur != par[cur]);
			back.push_back(cur);
		}
	}

	for (int i = 0; i < S; i++)
		for (int cur = X[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--)
			best = min(best, dis[X[i]][clv] + bestFor[cur]), assert(cur != par[cur]);

	for (int x : back)
		bestFor[x] = INF;
	back.clear();

	return best;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28280 KB Output is correct
2 Correct 358 ms 36984 KB Output is correct
3 Correct 444 ms 39500 KB Output is correct
4 Correct 479 ms 39544 KB Output is correct
5 Correct 438 ms 39988 KB Output is correct
6 Correct 318 ms 39032 KB Output is correct
7 Correct 389 ms 39716 KB Output is correct
8 Correct 378 ms 39804 KB Output is correct
9 Correct 445 ms 40108 KB Output is correct
10 Correct 300 ms 39032 KB Output is correct
11 Correct 421 ms 39536 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 27896 KB Output is correct
2 Correct 3431 ms 130168 KB Output is correct
3 Correct 5204 ms 155920 KB Output is correct
4 Correct 1125 ms 81564 KB Output is correct
5 Correct 6414 ms 209580 KB Output is correct
6 Correct 5094 ms 157156 KB Output is correct
7 Correct 1450 ms 60536 KB Output is correct
8 Correct 562 ms 50408 KB Output is correct
9 Correct 1659 ms 63920 KB Output is correct
10 Correct 1544 ms 61816 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28280 KB Output is correct
2 Correct 358 ms 36984 KB Output is correct
3 Correct 444 ms 39500 KB Output is correct
4 Correct 479 ms 39544 KB Output is correct
5 Correct 438 ms 39988 KB Output is correct
6 Correct 318 ms 39032 KB Output is correct
7 Correct 389 ms 39716 KB Output is correct
8 Correct 378 ms 39804 KB Output is correct
9 Correct 445 ms 40108 KB Output is correct
10 Correct 300 ms 39032 KB Output is correct
11 Correct 421 ms 39536 KB Output is correct
12 Correct 29 ms 27896 KB Output is correct
13 Correct 3431 ms 130168 KB Output is correct
14 Correct 5204 ms 155920 KB Output is correct
15 Correct 1125 ms 81564 KB Output is correct
16 Correct 6414 ms 209580 KB Output is correct
17 Correct 5094 ms 157156 KB Output is correct
18 Correct 1450 ms 60536 KB Output is correct
19 Correct 562 ms 50408 KB Output is correct
20 Correct 1659 ms 63920 KB Output is correct
21 Correct 1544 ms 61816 KB Output is correct
22 Correct 3774 ms 156924 KB Output is correct
23 Correct 4032 ms 159028 KB Output is correct
24 Correct 5729 ms 186424 KB Output is correct
25 Correct 5953 ms 189224 KB Output is correct
26 Correct 6204 ms 182980 KB Output is correct
27 Correct 7481 ms 237452 KB Output is correct
28 Correct 1530 ms 111256 KB Output is correct
29 Correct 5815 ms 182396 KB Output is correct
30 Correct 5613 ms 182200 KB Output is correct
31 Correct 5956 ms 182428 KB Output is correct
32 Correct 1768 ms 78948 KB Output is correct
33 Correct 545 ms 62952 KB Output is correct
34 Correct 1180 ms 66708 KB Output is correct
35 Correct 1156 ms 67192 KB Output is correct
36 Correct 1533 ms 70132 KB Output is correct
37 Correct 1645 ms 70156 KB Output is correct