oj.uz

답안 #409467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409467 2021-05-20T20:00:18 Z ScarletS 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 145988 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 12748 KB Output is correct
2 Correct 773 ms 30400 KB Output is correct
3 Correct 1408 ms 30692 KB Output is correct
4 Correct 1366 ms 30444 KB Output is correct
5 Correct 665 ms 30788 KB Output is correct
6 Correct 264 ms 30424 KB Output is correct
7 Correct 1363 ms 30720 KB Output is correct
8 Correct 1381 ms 30568 KB Output is correct
9 Correct 673 ms 30784 KB Output is correct
10 Correct 260 ms 30396 KB Output is correct
11 Correct 1358 ms 30664 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 12480 KB Output is correct
2 Correct 4821 ms 115188 KB Output is correct
3 Correct 6713 ms 117028 KB Output is correct
4 Correct 921 ms 115492 KB Output is correct
5 Correct 4880 ms 145988 KB Output is correct
6 Correct 7598 ms 118940 KB Output is correct
7 Correct 4928 ms 51540 KB Output is correct
8 Correct 438 ms 52072 KB Output is correct
9 Correct 2169 ms 55940 KB Output is correct
10 Correct 5186 ms 52936 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 12748 KB Output is correct
2 Correct 773 ms 30400 KB Output is correct
3 Correct 1408 ms 30692 KB Output is correct
4 Correct 1366 ms 30444 KB Output is correct
5 Correct 665 ms 30788 KB Output is correct
6 Correct 264 ms 30424 KB Output is correct
7 Correct 1363 ms 30720 KB Output is correct
8 Correct 1381 ms 30568 KB Output is correct
9 Correct 673 ms 30784 KB Output is correct
10 Correct 260 ms 30396 KB Output is correct
11 Correct 1358 ms 30664 KB Output is correct
12 Correct 10 ms 12480 KB Output is correct
13 Correct 4821 ms 115188 KB Output is correct
14 Correct 6713 ms 117028 KB Output is correct
15 Correct 921 ms 115492 KB Output is correct
16 Correct 4880 ms 145988 KB Output is correct
17 Correct 7598 ms 118940 KB Output is correct
18 Correct 4928 ms 51540 KB Output is correct
19 Correct 438 ms 52072 KB Output is correct
20 Correct 2169 ms 55940 KB Output is correct
21 Correct 5186 ms 52936 KB Output is correct
22 Correct 7759 ms 122280 KB Output is correct
23 Execution timed out 8022 ms 124972 KB Time limit exceeded
24 Halted 0 ms 0 KB -