oj.uz

Submission #384302

# Submission time Handle Problem Language Result Execution time Memory
384302 2021-04-01T09:47:08 Z shivensinha4 Factories (JOI14_factories) C++17
0 / 100
 8000 ms 353764 KB 
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
#ifndef mlocal
#include "factories.h"
#endif
 
int n;
vector<vector<array<ll, 2>>> adjList;
vi removed, subtreeSize, centroid;
vector<ll> whiteDist;
vector<vector<ll>> centroidDist;
const ll INF = 1e15;

void noteCentroidDist(int p, int parent) {
	ll d = centroidDist[p].back();
	for (auto i: adjList[p]) if (!removed[i[0]] and i[0] != parent) {
		centroidDist[i[0]].push_back(d+i[1]);
		noteCentroidDist(i[0], p);
	}
}
 
void decompose(int p, int c) {
	int invalidChild = -1, sizeLimit = (subtreeSize[p] >> 1);
	for (auto i: adjList[p]) if (!removed[i[0]] and subtreeSize[i[0]] > sizeLimit) {
			invalidChild = i[0];
			break;
		}
	
	if (invalidChild != -1) {
		subtreeSize[p] -= subtreeSize[invalidChild];
		subtreeSize[invalidChild] += subtreeSize[p];
		return decompose(invalidChild, c);
	}
	
	removed[p] = true;
	centroid[p] = c;
	
	centroidDist[p].push_back(0);
	noteCentroidDist(p, p);
	
	for (auto i: adjList[p]) if (!removed[i[0]]) {
		centroid[i[0]] = p;
		decompose(i[0], p);
	}
}
 
vi updated;
int pt = 0;
 
void update(int p) {
	int v = p, cpt = (int) centroidDist[p].size() - 1;
	while (v != -1) {
		ll d = centroidDist[p][cpt--];
		whiteDist[v] = min(whiteDist[v], d);
		updated[pt++] = v;
		v = centroid[v];
	}
}
 
ll ans(int p) {
	ll val = INF;
	int v = p,  cpt = (int) centroidDist[p].size() - 1;
	while (v != -1) {
		val = min(val, whiteDist[v] + centroidDist[p][cpt--]);
		v = centroid[v];
	}
	return (val == 1e9 ? -1 : val);
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	adjList.resize(n); subtreeSize.resize(n); removed.resize(n); centroid.resize(n, -1); whiteDist.resize(n, INF); updated.resize(10*n); centroidDist.resize(n);
	for_(i, 0, n-1) {
		int a = A[i], b = B[i]; ll w = D[i];
		adjList[a].push_back({b, w});
		adjList[b].push_back({a, w});
	}
	
	decompose(0, -1);
}
 
ll Query(int S, int X[], int T, int Y[]) {
	pt = 0;
	
	for_(i, 0, S) update(X[i]);
	ll val = INF;
	for_(i, 0, T) val = min(val, ans(Y[i]));
	for_(i, 0, pt) whiteDist[updated[i]] = INF;
	
	return val;
}
 
#ifdef mlocal
int main() {
	freopen("test.in", "r", stdin);
 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int N, q;
	cin >> N >> q;
	int A[100], B[100], D[100];
	for_(i, 0, N - 1) {
		int a, b, w;
		cin >> a >> b >> w;
		A[i] = a;
		B[i] = b;
		D[i] = w;
	}
 
	Init(N, A, B, D);
 
	int X[100], Y[100];
	while (q--) {
		int S, T;
		cin >> S >> T;
		for_(i, 0, S) cin >> X[i];
		for_(i, 0, T) cin >> Y[i];
		cout << Query(S, X, T, Y) << endl;
	}
 
	return 0;
}
#endif

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 748 KB Output is correct
2 Correct 480 ms 10092 KB Output is correct
3 Correct 3037 ms 19548 KB Output is correct
4 Runtime error 313 ms 37868 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 4672 ms 235068 KB Output is correct
3 Execution timed out 8044 ms 353764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 748 KB Output is correct
2 Correct 480 ms 10092 KB Output is correct
3 Correct 3037 ms 19548 KB Output is correct
4 Runtime error 313 ms 37868 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -