oj.uz

답안 #388890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388890 2021-04-13T09:00:22 Z saarang123 공장들 (JOI14_factories) C++17
15 / 100
 4037 ms 98832 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'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

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 12428 KB Output is correct
2 Correct 1144 ms 20824 KB Output is correct
3 Correct 1916 ms 20960 KB Output is correct
4 Correct 1820 ms 20952 KB Output is correct
5 Correct 2187 ms 21056 KB Output is correct
6 Correct 445 ms 20848 KB Output is correct
7 Correct 1840 ms 20880 KB Output is correct
8 Correct 1924 ms 20948 KB Output is correct
9 Correct 2094 ms 21064 KB Output is correct
10 Correct 440 ms 20832 KB Output is correct
11 Correct 1833 ms 20892 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Incorrect 4037 ms 98832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 12428 KB Output is correct
2 Correct 1144 ms 20824 KB Output is correct
3 Correct 1916 ms 20960 KB Output is correct
4 Correct 1820 ms 20952 KB Output is correct
5 Correct 2187 ms 21056 KB Output is correct
6 Correct 445 ms 20848 KB Output is correct
7 Correct 1840 ms 20880 KB Output is correct
8 Correct 1924 ms 20948 KB Output is correct
9 Correct 2094 ms 21064 KB Output is correct
10 Correct 440 ms 20832 KB Output is correct
11 Correct 1833 ms 20892 KB Output is correct
12 Correct 11 ms 12236 KB Output is correct
13 Incorrect 4037 ms 98832 KB Output isn't correct
14 Halted 0 ms 0 KB -