oj.uz

Submission #940886

# Submission time Handle Problem Language Result Execution time Memory
940886 2024-03-07T23:44:42 Z Leo121 Factories (JOI14_factories) C++17
100 / 100
 4907 ms 390176 KB 
#include <bits/stdc++.h>
#include "factories.h"

#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define SZ(v) int(v.size())
#define mp make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define SZ(v) int(v.size())
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef long double ld;
typedef double db;
typedef long long lli;
///typedef __int128 Int;

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
///const int inf = 1e4

const int MX = 2e5;
const ll inf = 5e14;

vector<vii> tree;
vector<int> subtree_size;
vector<bool> is_removed;
vector<vector<pair<int, ll>>> ancestors;
vector<ll> di;

int get_subtree_size(int u, int p = -1) {
	subtree_size[u] = 1;
	for (auto & [v, d] : tree[u]) {
		if (v == p || is_removed[v]) continue;
		subtree_size[u] += get_subtree_size(v, u);
	}
	return subtree_size[u];
}

int get_centroid(int u, int tree_size, int p = -1) {
	for (auto & [v, d] : tree[u]) {
		if (v == p || is_removed[v]) continue;
		if (subtree_size[v] * 2 > tree_size)
			return get_centroid(v, tree_size, u);
	}
	return u;
}

void get_dists(int u, int centroid, int p, ll dist) {
	for (auto & [v, d] : tree[u]) {
		if (v == p || is_removed[v]) continue;
		get_dists(v, centroid, u, dist + ll(d));
	}
	ancestors[u].push_back({centroid, dist});
}

void build_centroid_decomp(int u = 0) {
	int centroid = get_centroid(u, get_subtree_size(u));
	for (auto & [v, d] : tree[centroid]) {
		if (is_removed[v]) continue;
		get_dists(v, centroid, centroid, ll(d));
	}

	is_removed[centroid] = 1;
	for (auto & [v, d] : tree[centroid]) {
		if (is_removed[v]) continue;
		// build the centroid decomposition for all child components
		build_centroid_decomp(v);
	}
}

///t == 1 delete the info
///t == 0 update the info with the distance
void update(int u, bool t){
    di[u] = (t) ? inf : 0;
    for(auto & [v, d] : ancestors[u]) di[v] = (t) ? inf : min(di[v], d);
}

ll query(int u){
    ll ans = di[u];
    for(auto & [v, d] : ancestors[u]) ans = min(ans, di[v] + d);
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    is_removed.assign(N, 0);
    ancestors.assign(N, vector<pair<int, ll>>());
    tree.assign(N, vii());
    subtree_size.assign(N, 0);
    for0(i, N){
        tree[A[i]].pb({B[i], D[i]});
        tree[B[i]].pb({A[i], D[i]});
    }
    build_centroid_decomp(0);
    di.assign(N, inf);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = inf;
    for0(i, S) update(X[i], 0);
    for0(i, T) ans = min(ans, query(Y[i]));
    for0(i, S) update(X[i], 1);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17244 KB Output is correct
2 Correct 209 ms 31832 KB Output is correct
3 Correct 223 ms 32332 KB Output is correct
4 Correct 226 ms 32340 KB Output is correct
5 Correct 236 ms 32712 KB Output is correct
6 Correct 162 ms 31160 KB Output is correct
7 Correct 222 ms 32168 KB Output is correct
8 Correct 221 ms 32340 KB Output is correct
9 Correct 235 ms 32728 KB Output is correct
10 Correct 162 ms 31152 KB Output is correct
11 Correct 221 ms 32140 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 2318 ms 227256 KB Output is correct
3 Correct 3287 ms 339400 KB Output is correct
4 Correct 882 ms 129988 KB Output is correct
5 Correct 4197 ms 390176 KB Output is correct
6 Correct 3456 ms 339292 KB Output is correct
7 Correct 829 ms 83572 KB Output is correct
8 Correct 274 ms 53548 KB Output is correct
9 Correct 891 ms 95516 KB Output is correct
10 Correct 781 ms 83504 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17244 KB Output is correct
2 Correct 209 ms 31832 KB Output is correct
3 Correct 223 ms 32332 KB Output is correct
4 Correct 226 ms 32340 KB Output is correct
5 Correct 236 ms 32712 KB Output is correct
6 Correct 162 ms 31160 KB Output is correct
7 Correct 222 ms 32168 KB Output is correct
8 Correct 221 ms 32340 KB Output is correct
9 Correct 235 ms 32728 KB Output is correct
10 Correct 162 ms 31152 KB Output is correct
11 Correct 221 ms 32140 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 2318 ms 227256 KB Output is correct
14 Correct 3287 ms 339400 KB Output is correct
15 Correct 882 ms 129988 KB Output is correct
16 Correct 4197 ms 390176 KB Output is correct
17 Correct 3456 ms 339292 KB Output is correct
18 Correct 829 ms 83572 KB Output is correct
19 Correct 274 ms 53548 KB Output is correct
20 Correct 891 ms 95516 KB Output is correct
21 Correct 781 ms 83504 KB Output is correct
22 Correct 2844 ms 231624 KB Output is correct
23 Correct 2839 ms 233548 KB Output is correct
24 Correct 3875 ms 326272 KB Output is correct
25 Correct 3949 ms 333528 KB Output is correct
26 Correct 4000 ms 344276 KB Output is correct
27 Correct 4907 ms 385424 KB Output is correct
28 Correct 1062 ms 136916 KB Output is correct
29 Correct 3964 ms 343456 KB Output is correct
30 Correct 3770 ms 343436 KB Output is correct
31 Correct 3789 ms 344132 KB Output is correct
32 Correct 1030 ms 96084 KB Output is correct
33 Correct 296 ms 53716 KB Output is correct
34 Correct 574 ms 70964 KB Output is correct
35 Correct 597 ms 70892 KB Output is correct
36 Correct 806 ms 81908 KB Output is correct
37 Correct 859 ms 82404 KB Output is correct