oj.uz

Submission #388889

# Submission time Handle Problem Language Result Execution time Memory
388889 2021-04-13T08:59:15 Z saarang123 Factories (JOI14_factories) C++17
15 / 100
 4058 ms 98724 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 = 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 12328 KB Output is correct
2 Correct 1097 ms 20944 KB Output is correct
3 Correct 1887 ms 21040 KB Output is correct
4 Correct 1954 ms 20912 KB Output is correct
5 Correct 2188 ms 21256 KB Output is correct
6 Correct 440 ms 20960 KB Output is correct
7 Correct 1848 ms 20948 KB Output is correct
8 Correct 1994 ms 20920 KB Output is correct
9 Correct 2177 ms 21300 KB Output is correct
10 Correct 446 ms 20972 KB Output is correct
11 Correct 1856 ms 21108 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12236 KB Output is correct
2 Incorrect 4058 ms 98724 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 12328 KB Output is correct
2 Correct 1097 ms 20944 KB Output is correct
3 Correct 1887 ms 21040 KB Output is correct
4 Correct 1954 ms 20912 KB Output is correct
5 Correct 2188 ms 21256 KB Output is correct
6 Correct 440 ms 20960 KB Output is correct
7 Correct 1848 ms 20948 KB Output is correct
8 Correct 1994 ms 20920 KB Output is correct
9 Correct 2177 ms 21300 KB Output is correct
10 Correct 446 ms 20972 KB Output is correct
11 Correct 1856 ms 21108 KB Output is correct
12 Correct 13 ms 12236 KB Output is correct
13 Incorrect 4058 ms 98724 KB Output isn't correct
14 Halted 0 ms 0 KB -