oj.uz

Submission #563692

# Submission time Handle Problem Language Result Execution time Memory
563692 2022-05-18T02:19:22 Z hibiki Factories (JOI14_factories) C++11
100 / 100
 3729 ms 188956 KB 
#include"factories.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second

// global
int n;
vector<pair<int,long long> > v[500005];

// centroid
int cen[500005],sz[500005],deep[500005];
long long mn[500005],dist[500005][20];

int re_size(int nw,int fa)
{
    sz[nw] = 1;
    for(auto go: v[nw])
        if(go.f != fa && cen[go.f] == -1)
            sz[nw] += re_size(go.f,nw);
    return sz[nw];
}

int fi_cen(int nw,int fa,int sum)
{
    for(auto go: v[nw])
        if(go.f != fa && cen[go.f] == -1 && sz[go.f] > sum / 2)
            return fi_cen(go.f,nw,sum);
    return nw;
}

void get_dist(int nw,int fa,int lv)
{
    for(auto go: v[nw])
    {
        if(go.f != fa && cen[go.f] == -1)
        {
            dist[go.f][lv] = dist[nw][lv] + go.s;
            get_dist(go.f,nw,lv);
        }
    }
}

void centroid_decomp(int nw,int fa)
{
    int c = fi_cen(nw, -1, re_size(nw, -1));
    if(fa == -2) deep[c] = 0;
    else deep[c] = deep[fa] + 1;
    cen[c] = fa;
    mn[c] = 1e18;

    get_dist(c, -1, deep[c]);
    for(auto go: v[c])
        if(go.f != fa && cen[go.f] == -1)
            centroid_decomp(go.f, c);
}

void reset(int nw)
{
    int cur = nw;
    while(cur != -2)
    {
        mn[cur] = 1e18;
        cur = cen[cur];
    }
}

void cen_upd(int nw)
{
    int cur = nw;
    while(cur != -2)
    {
        mn[cur] = min(mn[cur],dist[nw][deep[cur]]);
        cur = cen[cur];
    }
}

long long cen_query(int nw)
{
    int cur = nw;
    long long ret = 1e18;
    while(cur != -2)
    {
        ret = min(ret,mn[cur] + dist[nw][deep[cur]]);
        cur = cen[cur];
    }
    return ret;
}

void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i = 0; i < n - 1; i++)
    {
        v[A[i]].pb({B[i],D[i]});
        v[B[i]].pb({A[i],D[i]});
    }

    memset(dist,0,sizeof(dist));
    memset(cen,-1,sizeof(cen));
    centroid_decomp(0, -2);

    return ;
}

long long Query(int S, int X[], int T, int Y[])
{
    long long ret = 1e18;
    for(int i = 0; i < S; i++)
        cen_upd(X[i]);
    for(int i = 0; i < T; i++)
        ret = min(ret,cen_query(Y[i]));
    for(int i = 0; i < S; i++)
        reset(X[i]);
    return ret;
}

// int a[500005],b[500005],c[500005];
// int ps[500005],pt[500005];
// int main()
// {
//     int n,q;
//     scanf("%d %d",&n,&q);
//     for(int i = 0; i < n - 1; i++)
//     {
//         scanf("%d %d %d",&a[i],&b[i],&c[i]);
//     }
//     Init(n, a, b, c);
//     for(int i = 0; i < q; i++)
//     {
//         int s,t;
//         scanf("%d %d",&s,&t);
//         for(int j = 0; j < s; j++)
//             scanf("%d",&ps[j]);
//         for(int j = 0; j < t; j++)
//             scanf("%d",&pt[j]);
//         printf("%lld\n",Query(s, ps, t, pt));
//     }
//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 92628 KB Output is correct
2 Correct 277 ms 100696 KB Output is correct
3 Correct 307 ms 100700 KB Output is correct
4 Correct 301 ms 100748 KB Output is correct
5 Correct 325 ms 100996 KB Output is correct
6 Correct 210 ms 100652 KB Output is correct
7 Correct 308 ms 100684 KB Output is correct
8 Correct 307 ms 100640 KB Output is correct
9 Correct 322 ms 100972 KB Output is correct
10 Correct 210 ms 100740 KB Output is correct
11 Correct 304 ms 100616 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 92408 KB Output is correct
2 Correct 1564 ms 138560 KB Output is correct
3 Correct 2471 ms 159516 KB Output is correct
4 Correct 562 ms 154552 KB Output is correct
5 Correct 3206 ms 184948 KB Output is correct
6 Correct 2479 ms 161884 KB Output is correct
7 Correct 723 ms 124044 KB Output is correct
8 Correct 346 ms 124088 KB Output is correct
9 Correct 875 ms 128968 KB Output is correct
10 Correct 767 ms 125548 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 92628 KB Output is correct
2 Correct 277 ms 100696 KB Output is correct
3 Correct 307 ms 100700 KB Output is correct
4 Correct 301 ms 100748 KB Output is correct
5 Correct 325 ms 100996 KB Output is correct
6 Correct 210 ms 100652 KB Output is correct
7 Correct 308 ms 100684 KB Output is correct
8 Correct 307 ms 100640 KB Output is correct
9 Correct 322 ms 100972 KB Output is correct
10 Correct 210 ms 100740 KB Output is correct
11 Correct 304 ms 100616 KB Output is correct
12 Correct 38 ms 92408 KB Output is correct
13 Correct 1564 ms 138560 KB Output is correct
14 Correct 2471 ms 159516 KB Output is correct
15 Correct 562 ms 154552 KB Output is correct
16 Correct 3206 ms 184948 KB Output is correct
17 Correct 2479 ms 161884 KB Output is correct
18 Correct 723 ms 124044 KB Output is correct
19 Correct 346 ms 124088 KB Output is correct
20 Correct 875 ms 128968 KB Output is correct
21 Correct 767 ms 125548 KB Output is correct
22 Correct 1815 ms 164332 KB Output is correct
23 Correct 1891 ms 167188 KB Output is correct
24 Correct 2991 ms 167724 KB Output is correct
25 Correct 3000 ms 171516 KB Output is correct
26 Correct 2967 ms 167808 KB Output is correct
27 Correct 3729 ms 188956 KB Output is correct
28 Correct 697 ms 165080 KB Output is correct
29 Correct 2990 ms 167504 KB Output is correct
30 Correct 2787 ms 167176 KB Output is correct
31 Correct 2990 ms 167800 KB Output is correct
32 Correct 903 ms 129376 KB Output is correct
33 Correct 341 ms 124532 KB Output is correct
34 Correct 585 ms 121664 KB Output is correct
35 Correct 598 ms 121644 KB Output is correct
36 Correct 757 ms 122432 KB Output is correct
37 Correct 813 ms 122468 KB Output is correct