oj.uz

Submission #879132

# Submission time Handle Problem Language Result Execution time Memory
879132 2023-11-26T12:08:38 Z serifefedartar Factories (JOI14_factories) C++17
100 / 100
 4203 ms 371908 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];
ll ans[MAXN];
vector<pair<int,ll>> anc[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 dfs(int node, int parent, int centro, ll dist) {
	for (auto u : graph[node]) {
		if (u.f == parent || marked[u.f]) 
			continue;
		dfs(u.f, node, centro, dist + u.s);
	}
	anc[node].push_back({centro, dist});
}

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

	marked[centro] = true;
	anc[centro].push_back({centro, 0});
	for (auto u : graph[centro]) {
		if (!marked[u.f])
			dfs(u.f, centro, centro, u.s);
	}

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

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]});
	}
	decompose(1, -1);

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

void add(int node) {
	for (auto u : anc[node])
		ans[u.f] = min(ans[u.f], u.s);
}

void remove(int node) {
	for (auto u : anc[node])
		ans[u.f] = 1e15;
}

ll qry(int node) {
	ll res = 1e15;
	for (auto u : anc[node])
		res = min(res, u.s + ans[u.f]);
	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 13 ms 35420 KB Output is correct
2 Correct 207 ms 40588 KB Output is correct
3 Correct 207 ms 41104 KB Output is correct
4 Correct 215 ms 41044 KB Output is correct
5 Correct 227 ms 41608 KB Output is correct
6 Correct 152 ms 40020 KB Output is correct
7 Correct 218 ms 41040 KB Output is correct
8 Correct 232 ms 41104 KB Output is correct
9 Correct 222 ms 41608 KB Output is correct
10 Correct 184 ms 40072 KB Output is correct
11 Correct 209 ms 41036 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 1841 ms 200588 KB Output is correct
3 Correct 2741 ms 271400 KB Output is correct
4 Correct 638 ms 97924 KB Output is correct
5 Correct 3618 ms 347572 KB Output is correct
6 Correct 2812 ms 289872 KB Output is correct
7 Correct 737 ms 88808 KB Output is correct
8 Correct 242 ms 65748 KB Output is correct
9 Correct 829 ms 102996 KB Output is correct
10 Correct 695 ms 89224 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 35420 KB Output is correct
2 Correct 207 ms 40588 KB Output is correct
3 Correct 207 ms 41104 KB Output is correct
4 Correct 215 ms 41044 KB Output is correct
5 Correct 227 ms 41608 KB Output is correct
6 Correct 152 ms 40020 KB Output is correct
7 Correct 218 ms 41040 KB Output is correct
8 Correct 232 ms 41104 KB Output is correct
9 Correct 222 ms 41608 KB Output is correct
10 Correct 184 ms 40072 KB Output is correct
11 Correct 209 ms 41036 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1841 ms 200588 KB Output is correct
14 Correct 2741 ms 271400 KB Output is correct
15 Correct 638 ms 97924 KB Output is correct
16 Correct 3618 ms 347572 KB Output is correct
17 Correct 2812 ms 289872 KB Output is correct
18 Correct 737 ms 88808 KB Output is correct
19 Correct 242 ms 65748 KB Output is correct
20 Correct 829 ms 102996 KB Output is correct
21 Correct 695 ms 89224 KB Output is correct
22 Correct 2060 ms 222144 KB Output is correct
23 Correct 2204 ms 226048 KB Output is correct
24 Correct 3298 ms 294328 KB Output is correct
25 Correct 3320 ms 296396 KB Output is correct
26 Correct 3147 ms 295572 KB Output is correct
27 Correct 4203 ms 371908 KB Output is correct
28 Correct 726 ms 122712 KB Output is correct
29 Correct 3113 ms 295036 KB Output is correct
30 Correct 2977 ms 295240 KB Output is correct
31 Correct 2926 ms 294992 KB Output is correct
32 Correct 922 ms 103248 KB Output is correct
33 Correct 255 ms 65772 KB Output is correct
34 Correct 496 ms 81900 KB Output is correct
35 Correct 513 ms 82812 KB Output is correct
36 Correct 676 ms 87892 KB Output is correct
37 Correct 691 ms 87668 KB Output is correct