oj.uz

Submission #66967

# Submission time Handle Problem Language Result Execution time Memory
66967 2018-08-13T01:36:15 Z imeimi2000 Factories (JOI14_factories) C++17
100 / 100
 4485 ms 195420 KB 
#include "factories.h"
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

struct _edge {
    int x, d;
    _edge(int x, int d) : x(x), d(d) {}
};

int n;
vector<_edge> edge[500001];

int dep[500001];
llong dist[500001];
int st[500001];
int ed[500001];
int par[500001][20];
void dfs(int x, int p) {
    static int ord = 0;
    st[x] = ++ord;
    par[x][0] = p;
    for (int i = 1; i < 20; ++i) {
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
    for (_edge i : edge[x]) {
        if (i.x == p) continue;
        dep[i.x] = dep[x] + 1;
        dist[i.x] = dist[x] + i.d;
        dfs(i.x, x);
    }
    ed[x] = ord;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; ++i) {
        ++A[i]; ++B[i];
        edge[A[i]].emplace_back(B[i], D[i]);
        edge[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(1, 0);
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i--; ) {
        if ((dep[x] - dep[y]) >> i) x = par[x][i];
    }
    if (x == y) return x;
    for (int i = 20; i--; ) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}

const llong inf = 1e16;
int in[500001];
int m, idx;
int qs[1000000];
llong ans;
pll dfs2() {
    llong d = dist[qs[idx]];
    llong mx = d + ((in[qs[idx]] == 1) ? 0 : inf);
    llong my = d + ((in[qs[idx]] == 2) ? 0 : inf);
    
    int e = ed[qs[idx++]];
    while (idx < m) {
        if (e < st[qs[idx]]) break;
        llong rx, ry;
        
        tie(rx, ry) = dfs2();
        ans = min({ ans, mx + ry - d - d, my + rx - d - d });
        mx = min(mx, rx);
        my = min(my, ry);
    }
    return pll(mx, my);
}

llong Query(int S, int X[], int T, int Y[]) {
    m = 0;
    for (int i = 0; i < S; ++i) {
        qs[m++] = ++X[i];
    }
    for (int i = 0; i < T; ++i) {
        qs[m++] = ++Y[i];
    }
    
    sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; });
    for (int i = 0; i + 1 < m; ++i) {
        qs[m + i] = lca(qs[i], qs[i + 1]);
    }
    m = (m << 1) - 1;
    sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; });
    m = unique(qs, qs + m) - qs;
    
    for (int i = 0; i < m; ++i) in[qs[i]] = 0;
    for (int i = 0; i < S; ++i) in[X[i]] = 1;
    for (int i = 0; i < T; ++i) in[Y[i]] = 2;
    
    idx = 0;
    ans = inf;
    dfs2();
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12664 KB Output is correct
2 Correct 1106 ms 30660 KB Output is correct
3 Correct 1057 ms 40064 KB Output is correct
4 Correct 1038 ms 49796 KB Output is correct
5 Correct 1002 ms 59540 KB Output is correct
6 Correct 727 ms 68780 KB Output is correct
7 Correct 1143 ms 78112 KB Output is correct
8 Correct 1069 ms 87692 KB Output is correct
9 Correct 992 ms 97256 KB Output is correct
10 Correct 681 ms 104020 KB Output is correct
11 Correct 948 ms 104028 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 104028 KB Output is correct
2 Correct 1981 ms 177712 KB Output is correct
3 Correct 2670 ms 178392 KB Output is correct
4 Correct 1379 ms 178452 KB Output is correct
5 Correct 2739 ms 195124 KB Output is correct
6 Correct 2776 ms 195124 KB Output is correct
7 Correct 2392 ms 195124 KB Output is correct
8 Correct 1232 ms 195124 KB Output is correct
9 Correct 2224 ms 195124 KB Output is correct
10 Correct 2157 ms 195124 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12664 KB Output is correct
2 Correct 1106 ms 30660 KB Output is correct
3 Correct 1057 ms 40064 KB Output is correct
4 Correct 1038 ms 49796 KB Output is correct
5 Correct 1002 ms 59540 KB Output is correct
6 Correct 727 ms 68780 KB Output is correct
7 Correct 1143 ms 78112 KB Output is correct
8 Correct 1069 ms 87692 KB Output is correct
9 Correct 992 ms 97256 KB Output is correct
10 Correct 681 ms 104020 KB Output is correct
11 Correct 948 ms 104028 KB Output is correct
12 Correct 18 ms 104028 KB Output is correct
13 Correct 1981 ms 177712 KB Output is correct
14 Correct 2670 ms 178392 KB Output is correct
15 Correct 1379 ms 178452 KB Output is correct
16 Correct 2739 ms 195124 KB Output is correct
17 Correct 2776 ms 195124 KB Output is correct
18 Correct 2392 ms 195124 KB Output is correct
19 Correct 1232 ms 195124 KB Output is correct
20 Correct 2224 ms 195124 KB Output is correct
21 Correct 2157 ms 195124 KB Output is correct
22 Correct 3361 ms 195124 KB Output is correct
23 Correct 3015 ms 195124 KB Output is correct
24 Correct 3424 ms 195124 KB Output is correct
25 Correct 3721 ms 195124 KB Output is correct
26 Correct 3729 ms 195124 KB Output is correct
27 Correct 3987 ms 195420 KB Output is correct
28 Correct 2149 ms 195420 KB Output is correct
29 Correct 3808 ms 195420 KB Output is correct
30 Correct 4034 ms 195420 KB Output is correct
31 Correct 4485 ms 195420 KB Output is correct
32 Correct 2062 ms 195420 KB Output is correct
33 Correct 1345 ms 195420 KB Output is correct
34 Correct 2147 ms 195420 KB Output is correct
35 Correct 1994 ms 195420 KB Output is correct
36 Correct 2389 ms 195420 KB Output is correct
37 Correct 2303 ms 195420 KB Output is correct