oj.uz

Submission #409468

# Submission time Handle Problem Language Result Execution time Memory
409468 2021-05-20T20:02:41 Z ScarletS Factories (JOI14_factories) C++17
33 / 100
 8000 ms 127352 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int N = 5e5+4, lg = 19;
const ll INF = 1e18;
int pt[N], sub[N], up[lg][N], tin[N], tout[N], ct;
ll h[N], ans[N];
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);
}

ll Query(int s, int x[], int t, int y[])
{
    for (int i=0;i<s;++i)
    {
        ++x[i];
        for (int j=x[i];j!=0;j=pt[j])
            ans[j]=min(ans[j],dist(x[i],j));
    }
    ll ret = INF;
    for (int i=0;i<t;++i)
    {
        ++y[i];
        for (int j=y[i];j!=0;j=pt[j])
            ret=min(ret,ans[j]+dist(y[i],j));
    }
    for (int i=0;i<s;++i)
        for (int j=x[i];j!=0;j=pt[j])
            ans[j]=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 24 ms 12492 KB Output is correct
2 Correct 769 ms 21036 KB Output is correct
3 Correct 1378 ms 21168 KB Output is correct
4 Correct 1313 ms 21264 KB Output is correct
5 Correct 655 ms 21376 KB Output is correct
6 Correct 254 ms 21020 KB Output is correct
7 Correct 1321 ms 21180 KB Output is correct
8 Correct 1355 ms 21364 KB Output is correct
9 Correct 655 ms 21260 KB Output is correct
10 Correct 251 ms 20932 KB Output is correct
11 Correct 1329 ms 21116 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12364 KB Output is correct
2 Correct 5015 ms 96732 KB Output is correct
3 Correct 6982 ms 99048 KB Output is correct
4 Correct 910 ms 97152 KB Output is correct
5 Correct 4971 ms 127352 KB Output is correct
6 Correct 7615 ms 100260 KB Output is correct
7 Correct 4943 ms 37944 KB Output is correct
8 Correct 412 ms 38228 KB Output is correct
9 Correct 2130 ms 41756 KB Output is correct
10 Correct 5087 ms 38928 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12492 KB Output is correct
2 Correct 769 ms 21036 KB Output is correct
3 Correct 1378 ms 21168 KB Output is correct
4 Correct 1313 ms 21264 KB Output is correct
5 Correct 655 ms 21376 KB Output is correct
6 Correct 254 ms 21020 KB Output is correct
7 Correct 1321 ms 21180 KB Output is correct
8 Correct 1355 ms 21364 KB Output is correct
9 Correct 655 ms 21260 KB Output is correct
10 Correct 251 ms 20932 KB Output is correct
11 Correct 1329 ms 21116 KB Output is correct
12 Correct 11 ms 12364 KB Output is correct
13 Correct 5015 ms 96732 KB Output is correct
14 Correct 6982 ms 99048 KB Output is correct
15 Correct 910 ms 97152 KB Output is correct
16 Correct 4971 ms 127352 KB Output is correct
17 Correct 7615 ms 100260 KB Output is correct
18 Correct 4943 ms 37944 KB Output is correct
19 Correct 412 ms 38228 KB Output is correct
20 Correct 2130 ms 41756 KB Output is correct
21 Correct 5087 ms 38928 KB Output is correct
22 Correct 7605 ms 97880 KB Output is correct
23 Execution timed out 8000 ms 100260 KB Time limit exceeded
24 Halted 0 ms 0 KB -