oj.uz

Submission #1028857

# Submission time Handle Problem Language Result Execution time Memory
1028857 2024-07-20T09:32:50 Z KienTran Factories (JOI14_factories) C++14
100 / 100
 3129 ms 296220 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

const int O = 2e6 + 5;
const int mod = 1e9 + 7; //998244353;
const long long inf = 1e16;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};

int n, q, Time, p[O], h[O], rp[O], in[O], child[O], f[22][O];
long long d[O], val[20][O];
vector <pair <int, int>> g[O];
pair <long long, int> dp[2][O];
bool del[O];

void init(int u, int par = -1){
    in[u] = ++ Time; rp[Time] = u;
    for (auto &to : g[u]){
        int v = to.first;
        int w = to.second;
        if (v != par){
            h[v] = h[u] + 1;
            d[v] = d[u] + w;
            init(v, u);
            rp[++ Time] = u;
        }
    }
}

int Lca(int u, int v){
    int l = min(in[u], in[v]);
    int r = max(in[u], in[v]);
    if (l == r) return u;

    int len = log2(r - l + 1);
    return h[f[len][l]] < h[f[len][r - (1 << len) + 1]] ? f[len][l] : f[len][r - (1 << len) + 1];
}

long long dist(int u, int v){
    return d[u] + d[v] - 2 * d[Lca(u, v)];
}

void dfs_init(int u, int par = -1){
    child[u] = 1;
    for (auto &to : g[u]){
        int v = to.first;
        int w = to.second;
        if (v != par && !del[v]){
            dfs_init(v, u);
            child[u] += child[v];
        }
    }
}

int centroid(int u, int par, int Nchild){
    for (auto &to : g[u]){
        int v = to.first;
        if (v != par && !del[v] && child[v] * 2 > Nchild) return centroid(v, u, Nchild);
    }
    return u;
}

int dfs_centroid(int u){
    dfs_init(u);
    int root = centroid(u, -1, child[u]);

    del[root] = 1;
    for (auto &v : g[root]){
        if (!del[v.first]){
            int nxt = dfs_centroid(v.first);
            p[nxt] = root;
        }
    }

    return root;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for (int i = 0; i < n - 1; ++ i){
        int u, v, w;
        u = A[i]; v = B[i]; w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    memset(p, -1, sizeof(p));

    init(0);

    for (int i = 1; i <= Time; ++ i){
        f[0][i] = rp[i];
    }

    for (int i = 1; i <= 21; ++ i){
        for (int j = 1; j - 1 + (1 << i) <= Time; ++ j){
            f[i][j] = h[f[i - 1][j]] < h[f[i - 1][j + (1 << (i - 1))]] ? f[i - 1][j] : f[i - 1][j + (1 << (i - 1))];
        }
    }

    dfs_centroid(0);

    for (int i = 0; i < n; ++ i){
        int u = i, cnt = 0;
        while (u != -1){
            val[cnt ++][i] = dist(i, u);
            u = p[u];
        }
    }

    for (int i = 0; i < n; ++ i) dp[0][i] = dp[1][i] = {inf, -1};
    return;
}

long long Query(int S, int X[], int T, int Y[]){
    long long res = inf;
    for (int i = 0; i < S; ++ i){
        int u = X[i], cnt = 0;
        pair <long long, int> cur = {0, -1};
        while (u != -1){
            cur.first = val[cnt ++][X[i]];
            if (dp[0][u].first > cur.first){
                pair <long long, int> x = dp[0][u];
                dp[0][u] = cur;
                if (cur.second != x.second) dp[1][u] = x;
            }
            else{
                if (dp[1][u].first > cur.first && cur.second != dp[0][u].second){
                    dp[1][u] = cur;
                }
            }
            cur.second = u;
            u = p[u];
        }
    }

    for (int i = 0; i < T; ++ i){
        int u = Y[i], cnt = 0;

        res = min(res, dp[0][u].first);
        while (u != -1){
            int par = p[u];
            if (par != -1){
                long long cur = val[++ cnt][Y[i]];
                res = min(res, cur + (dp[0][par].second == u ? dp[1][par].first : dp[0][par].first));
            }
            u = par;
        }
    }

    for (int i = 0; i < S; ++ i){
        int u = X[i];
        while (u != -1){
            dp[0][u] = dp[1][u] = {inf, -1};
            u = p[u];
        }
    }

    return res;
}

Compilation message

factories.cpp: In function 'void dfs_init(int, int)':
factories.cpp:48:13: warning: unused variable 'w' [-Wunused-variable]
   48 |         int w = to.second;
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55640 KB Output is correct
2 Correct 236 ms 64704 KB Output is correct
3 Correct 300 ms 64852 KB Output is correct
4 Correct 276 ms 64996 KB Output is correct
5 Correct 342 ms 65328 KB Output is correct
6 Correct 164 ms 64336 KB Output is correct
7 Correct 295 ms 64860 KB Output is correct
8 Correct 322 ms 65036 KB Output is correct
9 Correct 312 ms 65356 KB Output is correct
10 Correct 159 ms 64412 KB Output is correct
11 Correct 289 ms 65104 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 55644 KB Output is correct
2 Correct 1251 ms 249936 KB Output is correct
3 Correct 1855 ms 267860 KB Output is correct
4 Correct 456 ms 199348 KB Output is correct
5 Correct 2516 ms 296220 KB Output is correct
6 Correct 1894 ms 269192 KB Output is correct
7 Correct 668 ms 102384 KB Output is correct
8 Correct 229 ms 91332 KB Output is correct
9 Correct 820 ms 106860 KB Output is correct
10 Correct 673 ms 103796 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55640 KB Output is correct
2 Correct 236 ms 64704 KB Output is correct
3 Correct 300 ms 64852 KB Output is correct
4 Correct 276 ms 64996 KB Output is correct
5 Correct 342 ms 65328 KB Output is correct
6 Correct 164 ms 64336 KB Output is correct
7 Correct 295 ms 64860 KB Output is correct
8 Correct 322 ms 65036 KB Output is correct
9 Correct 312 ms 65356 KB Output is correct
10 Correct 159 ms 64412 KB Output is correct
11 Correct 289 ms 65104 KB Output is correct
12 Correct 23 ms 55644 KB Output is correct
13 Correct 1251 ms 249936 KB Output is correct
14 Correct 1855 ms 267860 KB Output is correct
15 Correct 456 ms 199348 KB Output is correct
16 Correct 2516 ms 296220 KB Output is correct
17 Correct 1894 ms 269192 KB Output is correct
18 Correct 668 ms 102384 KB Output is correct
19 Correct 229 ms 91332 KB Output is correct
20 Correct 820 ms 106860 KB Output is correct
21 Correct 673 ms 103796 KB Output is correct
22 Correct 1532 ms 250316 KB Output is correct
23 Correct 1563 ms 254816 KB Output is correct
24 Correct 2321 ms 269548 KB Output is correct
25 Correct 2245 ms 272976 KB Output is correct
26 Correct 2251 ms 269788 KB Output is correct
27 Correct 3129 ms 293028 KB Output is correct
28 Correct 512 ms 203448 KB Output is correct
29 Correct 2261 ms 269268 KB Output is correct
30 Correct 2321 ms 268624 KB Output is correct
31 Correct 2233 ms 269356 KB Output is correct
32 Correct 862 ms 107928 KB Output is correct
33 Correct 237 ms 91764 KB Output is correct
34 Correct 483 ms 97940 KB Output is correct
35 Correct 502 ms 98128 KB Output is correct
36 Correct 683 ms 101152 KB Output is correct
37 Correct 788 ms 101204 KB Output is correct