oj.uz

Submission #388898

# Submission time Handle Problem Language Result Execution time Memory
388898 2021-04-13T09:17:41 Z saarang123 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 117632 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], up[mxn][lgn], dt[mxn];
long long d[mxn], ans[mxn];
bool cent[mxn];
int n, m, cnt;

void dfs(int v, int p = 0) {
    up[v][0] = p;
    for(int i = 1; i < lgn; i++)
        up[v][i] = up[up[v][i - 1]][i - 1];
    for(auto &[u, w] : g[v]) if(u != p) {
        dt[u] = dt[v] + 1;
        d[u] = d[v] + w;
        dfs(u, v);
    }
}

int kth(int v, int diff) {
    for(int i = 0; i < lgn; i++)
        if(diff >> i & 1)
            v = up[v][i];
    return v;
}

int lca(int a, int b) {
    if(dt[a] > dt[b]) swap(a, b);
    b = kth(b, dt[b] - dt[a]);
    if(a == b) return a;
    for(int i = lgn - 1; i >= 0; i--)
        if(up[a][i] != up[b][i])
            a = up[a][i], b = up[b][i];
    return up[a][0];
}

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

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 decompose(int v, int p = -1) {
    cnt = dfssz(v);
    int centroid = fcent(v);
    par[centroid] = p;
    cent[centroid] = true;
    for(auto &[u, w] : g[centroid]) if(u != p && !cent[u])
        decompose(u, centroid);
}

void upd(int v) {
    for(int p = v; p != -1; p = par[p])
        ans[p] = min(ans[p], dist(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(v, p));
    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]});
	}
	dfs(0);
	decompose(0, -1);
	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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12424 KB Output is correct
2 Correct 1109 ms 20936 KB Output is correct
3 Correct 1855 ms 20972 KB Output is correct
4 Correct 1810 ms 21000 KB Output is correct
5 Correct 2099 ms 21056 KB Output is correct
6 Correct 440 ms 20848 KB Output is correct
7 Correct 1834 ms 21080 KB Output is correct
8 Correct 1905 ms 20940 KB Output is correct
9 Correct 2091 ms 21180 KB Output is correct
10 Correct 436 ms 20804 KB Output is correct
11 Correct 1837 ms 21012 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12236 KB Output is correct
2 Correct 3810 ms 98872 KB Output is correct
3 Execution timed out 8051 ms 117632 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12424 KB Output is correct
2 Correct 1109 ms 20936 KB Output is correct
3 Correct 1855 ms 20972 KB Output is correct
4 Correct 1810 ms 21000 KB Output is correct
5 Correct 2099 ms 21056 KB Output is correct
6 Correct 440 ms 20848 KB Output is correct
7 Correct 1834 ms 21080 KB Output is correct
8 Correct 1905 ms 20940 KB Output is correct
9 Correct 2091 ms 21180 KB Output is correct
10 Correct 436 ms 20804 KB Output is correct
11 Correct 1837 ms 21012 KB Output is correct
12 Correct 10 ms 12236 KB Output is correct
13 Correct 3810 ms 98872 KB Output is correct
14 Execution timed out 8051 ms 117632 KB Time limit exceeded
15 Halted 0 ms 0 KB -