Submission #409467

#	Time	Username	Problem	Language	Result	Execution time	Memory
409467		ScarletS	Factories (JOI14_factories)	C++17	33 / 100	8022 ms	145988 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67