oj.uz

Submission #409470

# Submission time Handle Problem Language Result Execution time Memory
409470 2021-05-20T20:15:38 Z ScarletS Factories (JOI14_factories) C++17
100 / 100
 4921 ms 285876 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e5+4, lg = 20;
const ll INF = 1e18;
int pt[N], sub[N], up[lg][N], tin[N], tout[N], ct;
ll h[N], ans[N];
pair<int,ll> lift[N][lg];
vector<array<int,2>> e[N];
bitset<N> b;

bool isAncestor(int x, int y)
{
    return (tin[x]<=tin[y]&&tout[y]<=tout[x]);
}

int lca(int x, int y)
{
    if (isAncestor(x,y))
        return x;
    if (isAncestor(y,x))
        return y;
    for (int i=lg-1;i>=0;--i)
        if (!isAncestor(up[i][x],y))
            x=up[i][x];
    return up[0][x];
}

ll dist(int x, int y)
{
    int z = lca(x,y);
    return h[x]+h[y]-h[z]*2;
}

void lcaDfs(int c, int p, ll x)
{
    tin[c]=++ct;
    h[c]=x;
    up[0][c]=p;
    for (int i=1;i<lg;++i)
        up[i][c]=up[i-1][up[i-1][c]];
    for (auto i : e[c])
        if (i[0]!=p)
            lcaDfs(i[0],c,x+i[1]);
    tout[c]=++ct;
}

void subDfs(int c, int p)
{
    sub[c]=1;
    for (auto i : e[c])
        if (i[0]!=p&&!b[i[0]])
        {
            subDfs(i[0],c);
            sub[c]+=sub[i[0]];
        }
}

void centDfs(int c, int p, int t)
{
    int mx=t-sub[c];
    for (auto i : e[c])
        if (i[0]!=p&&!b[i[0]])
        {
            centDfs(i[0],c,t);
            mx=max(mx,sub[i[0]]);
        }
    if (mx<=t/2)
        ct=c;
}

void solve(int r, int p)
{
    subDfs(r,0);
    centDfs(r,0,sub[r]);
    int X = ct;
    pt[X]=p;
    b[X]=1;
    for (auto i : e[X])
        if (!b[i[0]])
            solve(i[0],X);
}

void Init(int n, int A[], int B[], int w[])
{
    for (int i=0;i<n-1;++i)
    {
        ans[i+1]=INF;
        e[++A[i]].push_back({++B[i],w[i]});
        e[B[i]].push_back({A[i],w[i]});
    }
    ans[n]=INF;
    lcaDfs(1,0,0);
    tout[0]=++ct;
    solve(1,0);
    for (int i=1;i<=n;++i)
        for (int j=0,k=i;k!=0;++j,k=pt[k])
        {
            lift[i][j].first=k;
            lift[i][j].second=dist(i,k);
        }
}

ll Query(int s, int x[], int t, int y[])
{
    for (int i=0;i<s;++i)
    {
        ++x[i];
        for (int j=0;lift[x[i]][j].first!=0;++j)
            ans[lift[x[i]][j].first]=min(ans[lift[x[i]][j].first],lift[x[i]][j].second);
    }
    ll ret = INF;
    for (int i=0;i<t;++i)
    {
        ++y[i];
        for (int j=0;lift[y[i]][j].first!=0;++j)
            ret=min(ret,ans[lift[y[i]][j].first]+lift[y[i]][j].second);
    }
    for (int i=0;i<s;++i)
        for (int j=0;lift[x[i]][j].first!=0;++j)
            ans[lift[x[i]][j].first]=INF;
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12876 KB Output is correct
2 Correct 372 ms 23156 KB Output is correct
3 Correct 377 ms 23056 KB Output is correct
4 Correct 403 ms 23152 KB Output is correct
5 Correct 391 ms 23356 KB Output is correct
6 Correct 275 ms 23048 KB Output is correct
7 Correct 393 ms 23076 KB Output is correct
8 Correct 378 ms 23192 KB Output is correct
9 Correct 391 ms 23464 KB Output is correct
10 Correct 272 ms 23108 KB Output is correct
11 Correct 377 ms 23188 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12568 KB Output is correct
2 Correct 2640 ms 255152 KB Output is correct
3 Correct 4205 ms 257336 KB Output is correct
4 Correct 1008 ms 255944 KB Output is correct
5 Correct 4316 ms 285876 KB Output is correct
6 Correct 4170 ms 258636 KB Output is correct
7 Correct 1047 ms 70384 KB Output is correct
8 Correct 542 ms 70840 KB Output is correct
9 Correct 1071 ms 74592 KB Output is correct
10 Correct 1059 ms 71536 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12876 KB Output is correct
2 Correct 372 ms 23156 KB Output is correct
3 Correct 377 ms 23056 KB Output is correct
4 Correct 403 ms 23152 KB Output is correct
5 Correct 391 ms 23356 KB Output is correct
6 Correct 275 ms 23048 KB Output is correct
7 Correct 393 ms 23076 KB Output is correct
8 Correct 378 ms 23192 KB Output is correct
9 Correct 391 ms 23464 KB Output is correct
10 Correct 272 ms 23108 KB Output is correct
11 Correct 377 ms 23188 KB Output is correct
12 Correct 9 ms 12568 KB Output is correct
13 Correct 2640 ms 255152 KB Output is correct
14 Correct 4205 ms 257336 KB Output is correct
15 Correct 1008 ms 255944 KB Output is correct
16 Correct 4316 ms 285876 KB Output is correct
17 Correct 4170 ms 258636 KB Output is correct
18 Correct 1047 ms 70384 KB Output is correct
19 Correct 542 ms 70840 KB Output is correct
20 Correct 1071 ms 74592 KB Output is correct
21 Correct 1059 ms 71536 KB Output is correct
22 Correct 2964 ms 256800 KB Output is correct
23 Correct 3096 ms 259232 KB Output is correct
24 Correct 4827 ms 259344 KB Output is correct
25 Correct 4690 ms 263064 KB Output is correct
26 Correct 4633 ms 259592 KB Output is correct
27 Correct 4921 ms 282748 KB Output is correct
28 Correct 1300 ms 259612 KB Output is correct
29 Correct 4728 ms 259012 KB Output is correct
30 Correct 4757 ms 258356 KB Output is correct
31 Correct 4786 ms 259024 KB Output is correct
32 Correct 1156 ms 75160 KB Output is correct
33 Correct 607 ms 70844 KB Output is correct
34 Correct 848 ms 67828 KB Output is correct
35 Correct 857 ms 67832 KB Output is correct
36 Correct 1090 ms 68620 KB Output is correct
37 Correct 1063 ms 68620 KB Output is correct