oj.uz

Submission #587245

# Submission time Handle Problem Language Result Execution time Memory
587245 2022-07-01T14:15:19 Z danikoynov Factories (JOI14_factories) C++14
100 / 100
 4674 ms 297760 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
const ll inf = 1e18;

vector < pair < int, ll > > g[maxn];
int n, root, sub[maxn], used[maxn], par[maxn];
int f[2 * maxn], in[maxn], timer;
ll depth[maxn], cl[maxn];
void calc(int v, int p, bool st)
{
    if (st)
    {
        f[++ timer] = v;
        in[v] = timer;
    }
    sub[v] = 1;
    for (pair < int, ll > nb : g[v])
    {
        int u = nb.first;
        if (u == p || used[u])
            continue;
        if (st)
            depth[u] = depth[v] + nb.second;
        calc(u, v, st);
        sub[v] += sub[u];
        if (st)
            f[++ timer] = v;
    }
}

const int maxlog = 21;
ll dp[maxn * 2][maxlog], lg[maxn * 2];

void build_sparse_table()
{
    /**for (int i = 1; i <= timer; i ++)
        cout << f[i] << " ";
    cout << endl;*/
    for (int i = 1; i <= timer; i ++)
        dp[i][0] = depth[f[i]], lg[i] = lg[i / 2] + 1;

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j) + 1; i ++)
        {
            dp[i][j] = dp[i][j - 1];
            if (dp[i + (1 << (j - 1))][j - 1] < dp[i][j])
                dp[i][j] = dp[i + (1 << (j - 1))][j - 1];
        }

}

ll dist(int v, int u)
{
    int l = in[v], r = in[u];
    if (l > r)
        swap(l, r);

    int len = lg[r - l + 1] - 1;
    return depth[v] + depth[u] - 2 * min(dp[l][len], dp[r - (1 << len) + 1][len]);
}

int decompose(int v, int p, int sz)
{
    for (pair < int, ll > nb : g[v])
    {
        int u = nb.first;
        if (u == p || used[u])
            continue;
        if (sub[u] > sz / 2)
            return decompose(u, v, sz);
    }

    /// v is centroid
    used[v] = 1;

    for (pair < int, ll > nb : g[v])
    {
        int u = nb.first;
        if (used[u])
            continue;
        if (u == p)
            calc(u, v, 0);
        par[decompose(u, v, sub[u])] = v;
    }

    return v;
}
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], (ll)D[i]});
        g[B[i]].push_back({A[i], (ll)D[i]});
    }

    calc(0, -1, 1);
    root = decompose(0, -1, n);
    build_sparse_table();
    par[root] = -1;

    for (int i = 0; i < n; i ++)
        cl[i] = inf;
    ///cout << dist(2, 5) << endl;
}


ll Query(int S, int X[], int T, int Y[])
{
    ll ans = inf;
    for (int i = 0; i < S; i ++)
    {
        int v = X[i];
        while(v != par[root])
        {
            cl[v] = min(cl[v], dist(v, X[i]));
            v = par[v];
        }
    }

    for (int i = 0; i < T; i ++)
    {
        int u = Y[i];
        while(u != par[root])
        {
            ans = min(ans, cl[u] + dist(u, Y[i]));
            u = par[u];
        }
    }

    for (int i = 0; i < S; i ++)
    {
        int v = X[i];
        while(v != par[root])
        {
            cl[v] = inf;
            v = par[v];
        }
    }
    return ans;

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 344 ms 22264 KB Output is correct
3 Correct 386 ms 22360 KB Output is correct
4 Correct 377 ms 22344 KB Output is correct
5 Correct 445 ms 22724 KB Output is correct
6 Correct 225 ms 31852 KB Output is correct
7 Correct 409 ms 31520 KB Output is correct
8 Correct 410 ms 31796 KB Output is correct
9 Correct 465 ms 32128 KB Output is correct
10 Correct 228 ms 31868 KB Output is correct
11 Correct 383 ms 31768 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 1816 ms 242288 KB Output is correct
3 Correct 2549 ms 264004 KB Output is correct
4 Correct 992 ms 258272 KB Output is correct
5 Correct 3107 ms 295352 KB Output is correct
6 Correct 2697 ms 266124 KB Output is correct
7 Correct 1399 ms 80792 KB Output is correct
8 Correct 451 ms 80488 KB Output is correct
9 Correct 1620 ms 85524 KB Output is correct
10 Correct 1400 ms 82216 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 344 ms 22264 KB Output is correct
3 Correct 386 ms 22360 KB Output is correct
4 Correct 377 ms 22344 KB Output is correct
5 Correct 445 ms 22724 KB Output is correct
6 Correct 225 ms 31852 KB Output is correct
7 Correct 409 ms 31520 KB Output is correct
8 Correct 410 ms 31796 KB Output is correct
9 Correct 465 ms 32128 KB Output is correct
10 Correct 228 ms 31868 KB Output is correct
11 Correct 383 ms 31768 KB Output is correct
12 Correct 9 ms 12372 KB Output is correct
13 Correct 1816 ms 242288 KB Output is correct
14 Correct 2549 ms 264004 KB Output is correct
15 Correct 992 ms 258272 KB Output is correct
16 Correct 3107 ms 295352 KB Output is correct
17 Correct 2697 ms 266124 KB Output is correct
18 Correct 1399 ms 80792 KB Output is correct
19 Correct 451 ms 80488 KB Output is correct
20 Correct 1620 ms 85524 KB Output is correct
21 Correct 1400 ms 82216 KB Output is correct
22 Correct 2642 ms 268140 KB Output is correct
23 Correct 2820 ms 270728 KB Output is correct
24 Correct 3865 ms 272232 KB Output is correct
25 Correct 3923 ms 276132 KB Output is correct
26 Correct 3970 ms 272388 KB Output is correct
27 Correct 4674 ms 297760 KB Output is correct
28 Correct 1165 ms 268668 KB Output is correct
29 Correct 3794 ms 272068 KB Output is correct
30 Correct 3753 ms 271208 KB Output is correct
31 Correct 3720 ms 271916 KB Output is correct
32 Correct 1687 ms 86496 KB Output is correct
33 Correct 484 ms 81192 KB Output is correct
34 Correct 1078 ms 78196 KB Output is correct
35 Correct 1084 ms 78196 KB Output is correct
36 Correct 1333 ms 79112 KB Output is correct
37 Correct 1522 ms 79280 KB Output is correct