oj.uz

Submission #879108

# Submission time Handle Problem Language Result Execution time Memory
879108 2023-11-26T11:32:27 Z serifefedartar Factories (JOI14_factories) C++17
15 / 100
 8000 ms 140576 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 5e5 + 100;

vector<vector<pair<int,int>>> graph;
int marked[MAXN], sz[MAXN], up[LOGN][MAXN], depth[MAXN];
int par[MAXN];
ll depth_dist[MAXN], ans[MAXN];

int get_sz(int node, int parent) {
	sz[node] = 1;
	for (auto u : graph[node]) {
		if (u.f == parent || marked[u.f])
			continue;
		sz[node] += get_sz(u.f, node);
	}
	return sz[node];
}

int find_centro(int node, int parent, int n) {
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f] && sz[u.f] * 2 >= n)
			return find_centro(u.f, node, n);	
	}
	return node;
}

void decompose(int node, int parent) {
	int n = get_sz(node, node);
	int centro = find_centro(node, node, n);

	marked[centro] = true;
	par[centro] = parent;

	for (auto u : graph[centro]) {
		if (!marked[u.f])
			decompose(u.f, centro);
	}
}

void dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		depth[u.f] = depth[node] + 1;
		depth_dist[u.f] = depth_dist[node] + u.s;
		up[0][u.f] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u.f] = up[i-1][up[i-1][u.f]];
		dfs(u.f, node);
	}
}

int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);
	if (a == b)
		return a;

	for (int i = LOGN - 1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b];
		}
	}
	return up[0][a];
}

ll dist(int a, int b) {
	return depth_dist[a] + depth_dist[b] - 2 * depth_dist[lca(a, b)];
}

void Init(int N, int A[], int B[], int D[]) {
	graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 0; i < N-1; i++) {
		graph[A[i] + 1].push_back({B[i] + 1, D[i]});
		graph[B[i] + 1].push_back({A[i] + 1, D[i]});
	}

	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1;
	dfs(1, 1);
	decompose(1, -1);

	for (int i = 0; i < MAXN; i++)
		ans[i] = 1e15;
}

void add(int node) {
	int now = node;
	while (now != -1) {
		ans[now] = min(ans[now], dist(now, node));
		now = par[now];
	}
}

void remove(int node) {
	while (node != -1) {
		ans[node] = 1e15;
		node = par[node];
	}
}

ll qry(int node) {
	int now = node;
	ll res = 1e15;
	while (now != -1) {
		res = min(res, dist(now, node) + ans[now]);
		now = par[now];
	}
	return res;
}

ll Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++)
		add(X[i] + 1);

	ll mn = 1e15;
	for (int i = 0; i < T; i++)
		mn = min(mn, qry(Y[i] + 1));

	for (int i = 0; i < S; i++)
		remove(X[i] + 1);
	return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 67932 KB Output is correct
2 Correct 641 ms 72412 KB Output is correct
3 Correct 1174 ms 72528 KB Output is correct
4 Correct 1167 ms 72644 KB Output is correct
5 Correct 1261 ms 72756 KB Output is correct
6 Correct 214 ms 72272 KB Output is correct
7 Correct 1205 ms 72392 KB Output is correct
8 Correct 1199 ms 72484 KB Output is correct
9 Correct 1277 ms 72760 KB Output is correct
10 Correct 234 ms 72276 KB Output is correct
11 Correct 1177 ms 72476 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 67928 KB Output is correct
2 Correct 3016 ms 110720 KB Output is correct
3 Correct 6283 ms 114520 KB Output is correct
4 Correct 596 ms 111648 KB Output is correct
5 Execution timed out 8038 ms 140576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 67932 KB Output is correct
2 Correct 641 ms 72412 KB Output is correct
3 Correct 1174 ms 72528 KB Output is correct
4 Correct 1167 ms 72644 KB Output is correct
5 Correct 1261 ms 72756 KB Output is correct
6 Correct 214 ms 72272 KB Output is correct
7 Correct 1205 ms 72392 KB Output is correct
8 Correct 1199 ms 72484 KB Output is correct
9 Correct 1277 ms 72760 KB Output is correct
10 Correct 234 ms 72276 KB Output is correct
11 Correct 1177 ms 72476 KB Output is correct
12 Correct 10 ms 67928 KB Output is correct
13 Correct 3016 ms 110720 KB Output is correct
14 Correct 6283 ms 114520 KB Output is correct
15 Correct 596 ms 111648 KB Output is correct
16 Execution timed out 8038 ms 140576 KB Time limit exceeded
17 Halted 0 ms 0 KB -