oj.uz

Submission #409469

# Submission time Handle Problem Language Result Execution time Memory
409469 2021-05-20T20:13:36 Z ScarletS Factories (JOI14_factories) C++17
100 / 100
 5099 ms 307144 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
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;
}

// int main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     int n,q,s,t;
//     cin>>n>>q;
//     int a[n-1],b[n-1],c[n-1];
//     for (int i=0;i<n-1;++i)
//         cin>>a[i]>>b[i]>>c[i];
//     Init(n,a,b,c);
//     while (q--)
//     {
//         cin>>s>>t;
//         int x[s],y[t];
//         for (int i=0;i<s;++i)
//             cin>>x[i];
//         for (int i=0;i<t;++i)
//             cin>>y[i];
//         cout<<Query(s,x,t,y)<<"\n";
//     }
//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12760 KB Output is correct
2 Correct 352 ms 22652 KB Output is correct
3 Correct 380 ms 22576 KB Output is correct
4 Correct 374 ms 22592 KB Output is correct
5 Correct 390 ms 22832 KB Output is correct
6 Correct 306 ms 22596 KB Output is correct
7 Correct 373 ms 22512 KB Output is correct
8 Correct 371 ms 22588 KB Output is correct
9 Correct 391 ms 22972 KB Output is correct
10 Correct 273 ms 22528 KB Output is correct
11 Correct 369 ms 22572 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12492 KB Output is correct
2 Correct 2597 ms 254828 KB Output is correct
3 Correct 4129 ms 257388 KB Output is correct
4 Correct 1033 ms 255576 KB Output is correct
5 Correct 4340 ms 285908 KB Output is correct
6 Correct 4348 ms 258572 KB Output is correct
7 Correct 1051 ms 69256 KB Output is correct
8 Correct 545 ms 69852 KB Output is correct
9 Correct 1088 ms 73664 KB Output is correct
10 Correct 1074 ms 70584 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12760 KB Output is correct
2 Correct 352 ms 22652 KB Output is correct
3 Correct 380 ms 22576 KB Output is correct
4 Correct 374 ms 22592 KB Output is correct
5 Correct 390 ms 22832 KB Output is correct
6 Correct 306 ms 22596 KB Output is correct
7 Correct 373 ms 22512 KB Output is correct
8 Correct 371 ms 22588 KB Output is correct
9 Correct 391 ms 22972 KB Output is correct
10 Correct 273 ms 22528 KB Output is correct
11 Correct 369 ms 22572 KB Output is correct
12 Correct 10 ms 12492 KB Output is correct
13 Correct 2597 ms 254828 KB Output is correct
14 Correct 4129 ms 257388 KB Output is correct
15 Correct 1033 ms 255576 KB Output is correct
16 Correct 4340 ms 285908 KB Output is correct
17 Correct 4348 ms 258572 KB Output is correct
18 Correct 1051 ms 69256 KB Output is correct
19 Correct 545 ms 69852 KB Output is correct
20 Correct 1088 ms 73664 KB Output is correct
21 Correct 1074 ms 70584 KB Output is correct
22 Correct 2982 ms 256512 KB Output is correct
23 Correct 3135 ms 258852 KB Output is correct
24 Correct 4948 ms 283520 KB Output is correct
25 Correct 4735 ms 287352 KB Output is correct
26 Correct 4908 ms 283524 KB Output is correct
27 Correct 5099 ms 307144 KB Output is correct
28 Correct 1292 ms 284444 KB Output is correct
29 Correct 4971 ms 283284 KB Output is correct
30 Correct 4849 ms 282556 KB Output is correct
31 Correct 4795 ms 283404 KB Output is correct
32 Correct 1157 ms 88580 KB Output is correct
33 Correct 605 ms 84272 KB Output is correct
34 Correct 849 ms 80860 KB Output is correct
35 Correct 865 ms 80804 KB Output is correct
36 Correct 1049 ms 81544 KB Output is correct
37 Correct 1055 ms 81488 KB Output is correct