oj.uz

Submission #364327

# Submission time Handle Problem Language Result Execution time Memory
364327 2021-02-09T01:45:01 Z daniel920712 Factories (JOI14_factories) C++14
100 / 100
 6274 ms 301656 KB 
#include "factories.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <map>
using namespace std;
vector < pair < long long , long long > > Next[500005];
pair < long long , long long > Father[35][500005];
//min
long long vis[500005]={0};
long long use[500005]={0};
long long sz[500005]={0};
long long big[500005]={0};
long long tt[500005]={0};
long long root,now=1,now2=0;
pair < long long , long long > a[500005],b[500005];
vector < long long > have;
vector < int > how;
void F2(long long here)
{
    how.push_back(here);
    sz[here]=1;
    big[here]=0;
    vis[here]=now;
    for(auto i:Next[here])
    {
        if(!use[i.first]&&vis[i.first]!=now)
        {
            F2(i.first);
            sz[here]+=sz[i.first];
            big[here]=max(big[here],sz[i.first]);
        }
    }
}
void F3(long long here,long long root,long long fa,long long con,long long deg)
{
    Father[deg][here]=make_pair(root,con);
    for(auto i:Next[here])
    {
        if(i.first!=fa&&!use[i.first]) F3(i.first,root,here,con+i.second,deg);
    }
}
void F(long long here,long long deg)
{
    long long t=2e9;
    now++;
    how.clear();
    F2(here);
    for(auto i:how)
    {
        if(max(sz[here]-sz[i],big[i])<=t)
        {
            t=max(sz[here]-sz[i],big[i]);
            root=i;
        }
    }
    F3(root,root,-1,0,deg);
    use[root]=1;
    for(auto i:Next[root]) if(!use[i.first]) F(i.first,deg+1);
}
void Init(int N, int A[], int B[], int D[])
{

    int i,j;
    for(i=0;i<20;i++) for(j=0;j<N;j++) Father[i][j]=make_pair(-1,-1);
    for(i=0;i<N-1;i++)
    {
        Next[A[i]].push_back(make_pair((long long) B[i],(long long) D[i]));
        Next[B[i]].push_back(make_pair((long long) A[i],(long long) D[i]));
    }
    F(0,0);
}

long long Query(int S, int X[], int T, int Y[])
{
    long long ans=1e18,i,j;
    now2++;
    have.clear();
    for(i=0;i<S;i++)
    {
        for(j=0;j<20;j++)
        {
            if(Father[j][X[i]].first==-1) break;
            if(a[Father[j][X[i]].first].first!=now2) a[Father[j][X[i]].first]=make_pair(now2,Father[j][X[i]].second);
            else a[Father[j][X[i]].first].second=min(a[Father[j][X[i]].first].second,Father[j][X[i]].second);
            if(tt[Father[j][X[i]].first]!=now2)
            {
                have.push_back(Father[j][X[i]].first);
                tt[Father[j][X[i]].first]=now2;
            }

        }
    }

    for(i=0;i<T;i++)
    {
        for(j=0;j<20;j++)
        {
            if(Father[j][Y[i]].first==-1) break;
            if(b[Father[j][Y[i]].first].first!=now2) b[Father[j][Y[i]].first]=make_pair(now2,Father[j][Y[i]].second);
            else b[Father[j][Y[i]].first].second=min(b[Father[j][Y[i]].first].second,Father[j][Y[i]].second);
            if(tt[Father[j][Y[i]].first]!=now2)
            {
                have.push_back(Father[j][Y[i]].first);
                tt[Father[j][Y[i]].first]=now2;
            }


        }
    }

    for(auto i:have)
    {
        if(a[i].first!=now2||b[i].first!=now2) continue;
        ans=min(ans,a[i].second+b[i].second);
    }

    return ans;



}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12928 KB Output is correct
2 Correct 422 ms 32092 KB Output is correct
3 Correct 487 ms 32240 KB Output is correct
4 Correct 464 ms 32364 KB Output is correct
5 Correct 500 ms 32492 KB Output is correct
6 Correct 299 ms 32028 KB Output is correct
7 Correct 504 ms 32108 KB Output is correct
8 Correct 507 ms 32292 KB Output is correct
9 Correct 522 ms 32492 KB Output is correct
10 Correct 316 ms 32108 KB Output is correct
11 Correct 504 ms 32228 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12652 KB Output is correct
2 Correct 3042 ms 246296 KB Output is correct
3 Correct 4590 ms 251012 KB Output is correct
4 Correct 1120 ms 245560 KB Output is correct
5 Correct 5440 ms 280328 KB Output is correct
6 Correct 4707 ms 251036 KB Output is correct
7 Correct 2270 ms 81596 KB Output is correct
8 Correct 708 ms 81756 KB Output is correct
9 Correct 2572 ms 86412 KB Output is correct
10 Correct 2279 ms 83104 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12928 KB Output is correct
2 Correct 422 ms 32092 KB Output is correct
3 Correct 487 ms 32240 KB Output is correct
4 Correct 464 ms 32364 KB Output is correct
5 Correct 500 ms 32492 KB Output is correct
6 Correct 299 ms 32028 KB Output is correct
7 Correct 504 ms 32108 KB Output is correct
8 Correct 507 ms 32292 KB Output is correct
9 Correct 522 ms 32492 KB Output is correct
10 Correct 316 ms 32108 KB Output is correct
11 Correct 504 ms 32228 KB Output is correct
12 Correct 10 ms 12652 KB Output is correct
13 Correct 3042 ms 246296 KB Output is correct
14 Correct 4590 ms 251012 KB Output is correct
15 Correct 1120 ms 245560 KB Output is correct
16 Correct 5440 ms 280328 KB Output is correct
17 Correct 4707 ms 251036 KB Output is correct
18 Correct 2270 ms 81596 KB Output is correct
19 Correct 708 ms 81756 KB Output is correct
20 Correct 2572 ms 86412 KB Output is correct
21 Correct 2279 ms 83104 KB Output is correct
22 Correct 3482 ms 250304 KB Output is correct
23 Correct 3772 ms 251348 KB Output is correct
24 Correct 5242 ms 254148 KB Output is correct
25 Correct 5471 ms 279940 KB Output is correct
26 Correct 5566 ms 274688 KB Output is correct
27 Correct 6274 ms 301656 KB Output is correct
28 Correct 1446 ms 272712 KB Output is correct
29 Correct 5613 ms 274096 KB Output is correct
30 Correct 5662 ms 273372 KB Output is correct
31 Correct 5643 ms 273972 KB Output is correct
32 Correct 2289 ms 88164 KB Output is correct
33 Correct 684 ms 83348 KB Output is correct
34 Correct 1548 ms 79140 KB Output is correct
35 Correct 1561 ms 79044 KB Output is correct
36 Correct 2033 ms 80148 KB Output is correct
37 Correct 2094 ms 80100 KB Output is correct