oj.uz

Submission #364324

# Submission time Handle Problem Language Result Execution time Memory
364324 2021-02-09T01:39:49 Z daniel920712 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 371744 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 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<30;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<30;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);
            have.push_back(Father[j][X[i]].first);

        }
    }

    for(i=0;i<T;i++)
    {
        for(j=0;j<30;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);
            have.push_back(Father[j][Y[i]].first);

        }
    }

    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 20 ms 13164 KB Output is correct
2 Correct 593 ms 33132 KB Output is correct
3 Correct 732 ms 33284 KB Output is correct
4 Correct 716 ms 33384 KB Output is correct
5 Correct 818 ms 33896 KB Output is correct
6 Correct 303 ms 32876 KB Output is correct
7 Correct 716 ms 32876 KB Output is correct
8 Correct 725 ms 33384 KB Output is correct
9 Correct 804 ms 33788 KB Output is correct
10 Correct 309 ms 32876 KB Output is correct
11 Correct 724 ms 33212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12780 KB Output is correct
2 Correct 4124 ms 337268 KB Output is correct
3 Correct 5931 ms 340548 KB Output is correct
4 Correct 1205 ms 336612 KB Output is correct
5 Correct 7141 ms 371744 KB Output is correct
6 Correct 6238 ms 342712 KB Output is correct
7 Correct 4467 ms 96664 KB Output is correct
8 Correct 769 ms 96604 KB Output is correct
9 Correct 5080 ms 101236 KB Output is correct
10 Correct 4358 ms 98040 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 13164 KB Output is correct
2 Correct 593 ms 33132 KB Output is correct
3 Correct 732 ms 33284 KB Output is correct
4 Correct 716 ms 33384 KB Output is correct
5 Correct 818 ms 33896 KB Output is correct
6 Correct 303 ms 32876 KB Output is correct
7 Correct 716 ms 32876 KB Output is correct
8 Correct 725 ms 33384 KB Output is correct
9 Correct 804 ms 33788 KB Output is correct
10 Correct 309 ms 32876 KB Output is correct
11 Correct 724 ms 33212 KB Output is correct
12 Correct 10 ms 12780 KB Output is correct
13 Correct 4124 ms 337268 KB Output is correct
14 Correct 5931 ms 340548 KB Output is correct
15 Correct 1205 ms 336612 KB Output is correct
16 Correct 7141 ms 371744 KB Output is correct
17 Correct 6238 ms 342712 KB Output is correct
18 Correct 4467 ms 96664 KB Output is correct
19 Correct 769 ms 96604 KB Output is correct
20 Correct 5080 ms 101236 KB Output is correct
21 Correct 4358 ms 98040 KB Output is correct
22 Correct 5466 ms 352464 KB Output is correct
23 Correct 5695 ms 354508 KB Output is correct
24 Execution timed out 8048 ms 363960 KB Time limit exceeded
25 Halted 0 ms 0 KB -