oj.uz

답안 #388884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388884 2021-04-13T08:53:11 Z saarang123 공장들 (JOI14_factories) C++17
15 / 100
 1968 ms 27448 KB 
#include <bits/stdc++.h>
#ifndef saarang
#include "factories.h"
#endif
using namespace std;
const int mxn = 100 * 1000 + 3, lgn = 18;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3020 KB Output is correct
2 Correct 920 ms 11536 KB Output is correct
3 Correct 1643 ms 11388 KB Output is correct
4 Correct 1583 ms 11372 KB Output is correct
5 Correct 1895 ms 11640 KB Output is correct
6 Correct 466 ms 11368 KB Output is correct
7 Correct 1714 ms 11408 KB Output is correct
8 Correct 1761 ms 11376 KB Output is correct
9 Correct 1968 ms 11596 KB Output is correct
10 Correct 453 ms 11464 KB Output is correct
11 Correct 1643 ms 11388 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2764 KB Output is correct
2 Runtime error 400 ms 27448 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3020 KB Output is correct
2 Correct 920 ms 11536 KB Output is correct
3 Correct 1643 ms 11388 KB Output is correct
4 Correct 1583 ms 11372 KB Output is correct
5 Correct 1895 ms 11640 KB Output is correct
6 Correct 466 ms 11368 KB Output is correct
7 Correct 1714 ms 11408 KB Output is correct
8 Correct 1761 ms 11376 KB Output is correct
9 Correct 1968 ms 11596 KB Output is correct
10 Correct 453 ms 11464 KB Output is correct
11 Correct 1643 ms 11388 KB Output is correct
12 Correct 4 ms 2764 KB Output is correct
13 Runtime error 400 ms 27448 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -