Submission #1136929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136929		LeonidCuk	공장들 (JOI14_factories)	C++17	100 / 100	2844 ms	352088 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<pair<long long int,long long int>>g[500000],cd[500000],v(500000);
vector<int>sz(500000);
int m=1;
bool vis[500000]={0};
void dfs(int a,int b)
{
    sz[a]=1;
    for(auto p:g[a])
    {
        int i=p.first;
        if(i!=b&&vis[i]==0)
        {
            dfs(i,a);
            sz[a]+=sz[i];
        }
    }
}
void dfs2(int a,int b,long long int d,int k)
{
    cd[a].push_back({k,d});
    for(auto p:g[a])
    {
        int i=p.first;
        if(i!=b&&vis[i]==0)
        {
            dfs2(i,a,d+p.second,k);
        }
    }
}
void cen(int a)
{
    dfs(a,a);
    int n=sz[a],b=a;
    bool check=true;
    while(check)
    {
        check=false;
        for(auto p:g[a])
        {
            int i=p.first;
            if(i!=b&&vis[i]==0&&sz[i]*2>n)
            {
                check=true;
                b=a;
                a=i;
                break;
            }
        }
    }
    dfs2(a,a,0,a);
    vis[a]=1;
    for(auto p:g[a])
    {
        if(!vis[p.first])
        {
            cen(p.first);
        }
    }
}
void Init(int n, int a[], int b[], int c[])
{
    for(int i=0;i<n-1;i++)
    {
        g[a[i]].push_back({b[i],c[i]});
        g[b[i]].push_back({a[i],c[i]});
    }
    cen(0);
}
long long Query(int n1, int X[], int n2, int Y[])
{
        for(int i=0;i<n1;i++)
        {
            int a=X[i];
            for(int j=cd[a].size()-1;j>=0;j--)
            {
                auto p=cd[a][j];
                if(v[p.first].first!=m+1)
                {
                    v[p.first].second=p.second;
                    v[p.first].first=m+1;
                }
                else
                {
                    v[p.first].second=min(v[p.first].second,p.second);
                }
            }
        }
        long long ans=50000000000000;
        for(int i=0;i<n2;i++)
        {
            int a=Y[i];
            for(int j=cd[a].size()-1;j>=0;j--)
            {
                auto p=cd[a][j];
                if(v[p.first].first!=m+1)continue;
                else ans=min(ans,v[p.first].second+p.second);
            }
        }
        m++;
        return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67