Submission #364327

#	Time	Username	Problem	Language	Result	Execution time	Memory
364327		daniel920712	Factories (JOI14_factories)	C++14	100 / 100	6274 ms	301656 KiB

factories

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