oj.uz

답안 #388899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388899 2021-04-13T09:19:36 Z saarang123 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 100652 KB 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#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;
}

Compilation message

factories.cpp:1: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    1 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 12332 KB Output is correct
2 Correct 928 ms 20816 KB Output is correct
3 Correct 1735 ms 20964 KB Output is correct
4 Correct 1705 ms 20852 KB Output is correct
5 Correct 1873 ms 21148 KB Output is correct
6 Correct 472 ms 20836 KB Output is correct
7 Correct 1770 ms 20984 KB Output is correct
8 Correct 1814 ms 20860 KB Output is correct
9 Correct 1920 ms 21184 KB Output is correct
10 Correct 390 ms 20832 KB Output is correct
11 Correct 1699 ms 20980 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12236 KB Output is correct
2 Correct 3871 ms 99008 KB Output is correct
3 Execution timed out 8022 ms 100652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 12332 KB Output is correct
2 Correct 928 ms 20816 KB Output is correct
3 Correct 1735 ms 20964 KB Output is correct
4 Correct 1705 ms 20852 KB Output is correct
5 Correct 1873 ms 21148 KB Output is correct
6 Correct 472 ms 20836 KB Output is correct
7 Correct 1770 ms 20984 KB Output is correct
8 Correct 1814 ms 20860 KB Output is correct
9 Correct 1920 ms 21184 KB Output is correct
10 Correct 390 ms 20832 KB Output is correct
11 Correct 1699 ms 20980 KB Output is correct
12 Correct 13 ms 12236 KB Output is correct
13 Correct 3871 ms 99008 KB Output is correct
14 Execution timed out 8022 ms 100652 KB Time limit exceeded
15 Halted 0 ms 0 KB -