oj.uz

Submission #388886

# Submission time Handle Problem Language Result Execution time Memory
388886 2021-04-13T08:55:15 Z saarang123 Factories (JOI14_factories) C++17
15 / 100
 3856 ms 96884 KB 
#include <bits/stdc++.h>
#ifndef saarang
#include "factories.h"
#endif
using namespace std;
const int mxn = 500 * 1000 + 3, lgn = 20;
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 = 1) {
    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, -1);
	decompose(0, -1);
	for(int i = 0; i <= n; i++)
        ans[i] = 1'000'000'000'000'0000;
}

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 29 ms 12620 KB Output is correct
2 Correct 1069 ms 21268 KB Output is correct
3 Correct 1889 ms 21432 KB Output is correct
4 Correct 1827 ms 21536 KB Output is correct
5 Correct 2083 ms 21688 KB Output is correct
6 Correct 429 ms 21316 KB Output is correct
7 Correct 1790 ms 21580 KB Output is correct
8 Correct 1887 ms 21360 KB Output is correct
9 Correct 2128 ms 21604 KB Output is correct
10 Correct 438 ms 21280 KB Output is correct
11 Correct 1793 ms 21264 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Incorrect 3856 ms 96884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12620 KB Output is correct
2 Correct 1069 ms 21268 KB Output is correct
3 Correct 1889 ms 21432 KB Output is correct
4 Correct 1827 ms 21536 KB Output is correct
5 Correct 2083 ms 21688 KB Output is correct
6 Correct 429 ms 21316 KB Output is correct
7 Correct 1790 ms 21580 KB Output is correct
8 Correct 1887 ms 21360 KB Output is correct
9 Correct 2128 ms 21604 KB Output is correct
10 Correct 438 ms 21280 KB Output is correct
11 Correct 1793 ms 21264 KB Output is correct
12 Correct 11 ms 12236 KB Output is correct
13 Incorrect 3856 ms 96884 KB Output isn't correct
14 Halted 0 ms 0 KB -