oj.uz

Submission #388906

# Submission time Handle Problem Language Result Execution time Memory
388906 2021-04-13T09:36:58 Z saarang123 Factories (JOI14_factories) C++17
100 / 100
 6061 ms 171004 KB 
#include <bits/stdc++.h>
#ifndef saarang
#include "factories.h"
#endif
using namespace std;
const int mxn = 500 * 1000 + 3, lgn = 21;
vector<array<int, 2>> g[mxn];
int sz[mxn], par[mxn], dt[mxn], lvl[mxn];
long long d[mxn], ans[mxn], dist[lgn][mxn];
bool cent[mxn];
int n, m, cnt;

int dfssz(int v, int p = -1) {
    sz[v] = 1;
    for(auto &[u, w] : g[v]) if(u != p && !cent[u])
        sz[v] += dfssz(u, v);
    return sz[v];
}

int fcent(int v, int p = -1) {
    for(auto &[u, w] : g[v]) if(u != p && !cent[u])
        if(sz[u] > cnt / 2)
            return fcent(u, v);
    return v;
}

void fdist(int v, int p, int l) {
	for(auto &[u, w] : g[v]) if(u != p && !cent[u]) {
		dist[l][u] = dist[l][v] + w;
		fdist(u, v, l);
	}
}

void decompose(int v, int p = -1, int dep = 0) {
    cnt = dfssz(v);
    int centroid = fcent(v);
    par[centroid] = p;
    lvl[centroid] = dep;
    dist[dep][centroid] = 0;
    fdist(centroid, -1, dep);
    cent[centroid] = true;
    for(auto &[u, w] : g[centroid]) if(u != p && !cent[u])
        decompose(u, centroid, dep + 1);
}

void upd(int v) {
    for(int p = v; p != -1; p = par[p])
        ans[p] = min(ans[p], dist[lvl[p]][v]);
}

long long qry(int v) {
    long long res = ans[n];
    for(int p = v; p != -1; p = par[p])
        res = min(res, ans[p] + dist[lvl[p]][v]);
    return res;
}

void fix(int v) {
	for(int p = v; p != -1; p = par[p])
		ans[p] = ans[n];
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++) {
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	decompose(0, -1, 0);
	for(int i = 0; i <= n; i++)
        ans[i] = 1'000'000'000'000'000'000;
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < T; i++)
		upd(Y[i]);
	long long answer = ans[n];
	for(int i = 0; i < S; i++)
		answer = min(answer, qry(X[i]));
	for(int i = 0; i < T; i++)
		fix(Y[i]);
	return answer;
}

#ifdef saarang
signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    int N, Q;
    cin >> N >> Q;
    int A[N - 1], B[N - 1], D[N - 1];
    for(int i = 0; i < N - 1; i++) 
    	cin >> A[i] >> B[i] >> D[i];
    Init(N, A, B, D);
    while(Q--) {
    	int S, T;
    	cin >> S >> T;
    	int X[S], Y[T];
    	for(int i = 0; i < S; i++)
    		cin >> X[i];
    	for(int i = 0; i < T; i++)
    		cin >> Y[i];
    	cout << Query(S, X, T, Y) << '\n';
    }
    return 0;
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12492 KB Output is correct
2 Correct 375 ms 21000 KB Output is correct
3 Correct 401 ms 21060 KB Output is correct
4 Correct 395 ms 21200 KB Output is correct
5 Correct 488 ms 21368 KB Output is correct
6 Correct 286 ms 20592 KB Output is correct
7 Correct 409 ms 21276 KB Output is correct
8 Correct 425 ms 21196 KB Output is correct
9 Correct 446 ms 21292 KB Output is correct
10 Correct 274 ms 20552 KB Output is correct
11 Correct 404 ms 21040 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12236 KB Output is correct
2 Correct 2499 ms 112844 KB Output is correct
3 Correct 3734 ms 129808 KB Output is correct
4 Correct 827 ms 80588 KB Output is correct
5 Correct 4942 ms 171004 KB Output is correct
6 Correct 3890 ms 149764 KB Output is correct
7 Correct 1224 ms 55992 KB Output is correct
8 Correct 415 ms 45056 KB Output is correct
9 Correct 1452 ms 59540 KB Output is correct
10 Correct 1236 ms 57456 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12492 KB Output is correct
2 Correct 375 ms 21000 KB Output is correct
3 Correct 401 ms 21060 KB Output is correct
4 Correct 395 ms 21200 KB Output is correct
5 Correct 488 ms 21368 KB Output is correct
6 Correct 286 ms 20592 KB Output is correct
7 Correct 409 ms 21276 KB Output is correct
8 Correct 425 ms 21196 KB Output is correct
9 Correct 446 ms 21292 KB Output is correct
10 Correct 274 ms 20552 KB Output is correct
11 Correct 404 ms 21040 KB Output is correct
12 Correct 10 ms 12236 KB Output is correct
13 Correct 2499 ms 112844 KB Output is correct
14 Correct 3734 ms 129808 KB Output is correct
15 Correct 827 ms 80588 KB Output is correct
16 Correct 4942 ms 171004 KB Output is correct
17 Correct 3890 ms 149764 KB Output is correct
18 Correct 1224 ms 55992 KB Output is correct
19 Correct 415 ms 45056 KB Output is correct
20 Correct 1452 ms 59540 KB Output is correct
21 Correct 1236 ms 57456 KB Output is correct
22 Correct 2941 ms 137600 KB Output is correct
23 Correct 3074 ms 135992 KB Output is correct
24 Correct 4712 ms 155832 KB Output is correct
25 Correct 4729 ms 152164 KB Output is correct
26 Correct 4605 ms 137684 KB Output is correct
27 Correct 6061 ms 161720 KB Output is correct
28 Correct 1026 ms 73080 KB Output is correct
29 Correct 4792 ms 138228 KB Output is correct
30 Correct 4710 ms 137880 KB Output is correct
31 Correct 4680 ms 138264 KB Output is correct
32 Correct 1433 ms 60724 KB Output is correct
33 Correct 422 ms 45496 KB Output is correct
34 Correct 908 ms 51176 KB Output is correct
35 Correct 895 ms 51216 KB Output is correct
36 Correct 1222 ms 54248 KB Output is correct
37 Correct 1225 ms 54320 KB Output is correct