oj.uz

Submission #879106

# Submission time Handle Problem Language Result Execution time Memory
879106 2023-11-26T11:13:50 Z serifefedartar Factories (JOI14_factories) C++17
15 / 100
 8000 ms 159212 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 = 1e16;
	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 21 ms 67932 KB Output is correct
2 Correct 556 ms 81744 KB Output is correct
3 Correct 1117 ms 82004 KB Output is correct
4 Correct 1090 ms 81744 KB Output is correct
5 Correct 1249 ms 82208 KB Output is correct
6 Correct 220 ms 81748 KB Output is correct
7 Correct 1113 ms 82116 KB Output is correct
8 Correct 1164 ms 82004 KB Output is correct
9 Correct 1261 ms 82360 KB Output is correct
10 Correct 214 ms 81744 KB Output is correct
11 Correct 1131 ms 81940 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 67932 KB Output is correct
2 Correct 2879 ms 129372 KB Output is correct
3 Correct 5852 ms 132372 KB Output is correct
4 Correct 595 ms 129944 KB Output is correct
5 Execution timed out 8013 ms 159212 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 67932 KB Output is correct
2 Correct 556 ms 81744 KB Output is correct
3 Correct 1117 ms 82004 KB Output is correct
4 Correct 1090 ms 81744 KB Output is correct
5 Correct 1249 ms 82208 KB Output is correct
6 Correct 220 ms 81748 KB Output is correct
7 Correct 1113 ms 82116 KB Output is correct
8 Correct 1164 ms 82004 KB Output is correct
9 Correct 1261 ms 82360 KB Output is correct
10 Correct 214 ms 81744 KB Output is correct
11 Correct 1131 ms 81940 KB Output is correct
12 Correct 14 ms 67932 KB Output is correct
13 Correct 2879 ms 129372 KB Output is correct
14 Correct 5852 ms 132372 KB Output is correct
15 Correct 595 ms 129944 KB Output is correct
16 Execution timed out 8013 ms 159212 KB Time limit exceeded
17 Halted 0 ms 0 KB -