oj.uz

답안 #713598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713598 2023-03-22T15:42:25 Z Spade1 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 439776 KB 
#include <bits/stdc++.h>
#include "factories.h"
//#include "grader.cpp"
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define pb push_back
#define INF 1e18
using namespace std;

const int maxN = 500050;
const int L = log2(maxN) + 10;

vector<pll> adj[maxN];
set<ll> s;
bool mark[maxN];
ll sz[maxN], mn[maxN], up[maxN], dist[maxN][L], lvl[maxN], P[maxN][L], updist[maxN][L];

void dfs2(int a, int prt, ll cur) {
    lvl[a] = lvl[prt]+1;
    P[a][0] = prt;
    updist[a][0] = cur;
    for (int i = 1; i < L; ++i) {
        P[a][i] = P[P[a][i-1]][i-1];
        updist[a][i] = updist[P[a][i-1]][i-1] + updist[a][i-1];
    }
    for (auto [b, w] : adj[a]) if (b != prt) dfs2(b, a, w);
}

long long lca(int a, int b) {
    if (lvl[a] < lvl[b]) swap(a, b);
    int j = lvl[a] - lvl[b];
    ll dis = 0;
    for (int i = 0; i < L; ++i) {
        if (j & (1<<i)) {
            dis += updist[a][i];
            a = P[a][i];
        }
    }
    if (a==b) return dis;
    for (int i = L-1; i >= 0; --i) {
        if (P[a][i] != P[b][i]) {
            dis += (updist[a][i] + updist[b][i]);
            a = P[a][i]; b = P[b][i];
        }
    }
    return dis + updist[a][0] + updist[b][0];
}

void computedist(int n) {
    for (int i = 0; i < n; ++i) {
        int cnt = 0;
        for (int j = i; j != -1; j = up[j]) {
            dist[i][cnt++] = lca(i, j);
        }
    }
}

int dfs(int i, int prt=-1) {
    sz[i] = 1;
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        sz[i] += dfs(j, i);
    }
    return sz[i];
}

int find_centroid(int i, int m, int prt=-1) {
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        if (sz[j] > m/2) return find_centroid(j, m, i);
    }
    return i;
}

int decom(int x=0) {
    int cen = find_centroid(x, dfs(x));
    mark[cen] = 1;

    for (auto [j, w] : adj[cen]) {
        if (mark[j]) continue;
        int c = decom(j);
        up[c] = cen;
    }
    return cen;
}

void update(int v) {
    int cur = v, cnt = 0;
    while (cur != -1) {
        s.insert(cur);
        mn[cur] = min(mn[cur], dist[v][cnt]);
        cur = up[cur];
        cnt++;
    }
}

ll query(int v) {
    ll ans = INF, cur = v, cnt = 0;
    while (cur != -1) {
        ans = min(ans, mn[cur] + dist[v][cnt]);
        cur = up[cur];
        cnt++;
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++i) {
        adj[A[i]].pb({B[i], D[i]});
        adj[B[i]].pb({A[i], D[i]});
    }
    for (int i = 0; i < N; ++i) mn[i] = INF;
    memset(up, -1, sizeof(up));
    decom();
    dfs2(0, -1, 0);
    computedist(N);
}

ll Query(int S, int X[], int T, int Y[]) {
    s.clear();
    for (int i = 0; i < S; ++i) update(X[i]);
    ll ans = INF;
    for (int i = 0; i < T; ++i) ans = min(ans, query(Y[i]));
    for (auto i : s) mn[i] = INF;
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs2(int, int, long long int)':
factories.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for (auto [b, w] : adj[a]) if (b != prt) dfs2(b, a, w);
      |               ^
factories.cpp: In function 'int dfs(int, int)':
factories.cpp:63:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:71:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'int decom(int)':
factories.cpp:82:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for (auto [j, w] : adj[cen]) {
      |               ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 16596 KB Output is correct
2 Correct 695 ms 27784 KB Output is correct
3 Correct 830 ms 27836 KB Output is correct
4 Correct 834 ms 27964 KB Output is correct
5 Correct 1014 ms 28312 KB Output is correct
6 Correct 331 ms 27724 KB Output is correct
7 Correct 816 ms 27836 KB Output is correct
8 Correct 814 ms 27884 KB Output is correct
9 Correct 996 ms 28248 KB Output is correct
10 Correct 367 ms 27708 KB Output is correct
11 Correct 819 ms 27976 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16468 KB Output is correct
2 Correct 2973 ms 414032 KB Output is correct
3 Correct 5688 ms 416256 KB Output is correct
4 Correct 883 ms 411404 KB Output is correct
5 Execution timed out 8026 ms 439776 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 16596 KB Output is correct
2 Correct 695 ms 27784 KB Output is correct
3 Correct 830 ms 27836 KB Output is correct
4 Correct 834 ms 27964 KB Output is correct
5 Correct 1014 ms 28312 KB Output is correct
6 Correct 331 ms 27724 KB Output is correct
7 Correct 816 ms 27836 KB Output is correct
8 Correct 814 ms 27884 KB Output is correct
9 Correct 996 ms 28248 KB Output is correct
10 Correct 367 ms 27708 KB Output is correct
11 Correct 819 ms 27976 KB Output is correct
12 Correct 11 ms 16468 KB Output is correct
13 Correct 2973 ms 414032 KB Output is correct
14 Correct 5688 ms 416256 KB Output is correct
15 Correct 883 ms 411404 KB Output is correct
16 Execution timed out 8026 ms 439776 KB Time limit exceeded
17 Halted 0 ms 0 KB -