Submission #360198

#	Time	Username	Problem	Language	Result	Execution time	Memory
360198		shahriarkhan	Factories (JOI14_factories)	C++14	100 / 100	3904 ms	193652 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std ;

const int mx = 5e5 + 10 ;
const long long INF = 1e18 ;

vector<pair<int,long long> > edges[mx] ;

int n , sub[mx] , par[mx] , depth[mx] , vis[mx] ;

long long ans[mx] , dist[mx][20] ;

stack<int> st ;

void dfs(int x , int p , int d)
{
    sub[x] = 1 ;
    for(auto i : edges[x])
    {
        if(i.first == p) continue ;
        if(vis[i.first]) continue ;
        if(d) dist[i.first][d-1] = dist[x][d-1] + i.second ;
        dfs(i.first,x,d) ;
        sub[x] += sub[i.first] ;
    }
}

int find_centroid(int x , int p , int range)
{
    for(auto i : edges[x])
    {
        if(i.first==p) continue ;
        if(vis[i.first]) continue ;
        if(sub[i.first]>range)
        {
            return find_centroid(i.first,x,range) ;
        }
    }
    return x ;
}

void build(int x , int p , int d)
{
    dfs(x,-1,d) ;
    int c = find_centroid(x,-1,sub[x]/2) ;
    par[c] = p , vis[c] = 1 , depth[c] = d ;
    for(auto i : edges[c])
    {
        if(vis[i.first]) continue ;
        dist[i.first][d] = i.second ;
        build(i.first,c,d+1) ;
    }
    vis[c] = 0 ;
}

void update(int x)
{
    int cur = x ;
    while(cur)
    {
        ans[cur] = min(ans[cur],dist[x][depth[cur]]) ;
        st.push(cur) ;
        cur = par[cur] ;
    }
}

long long query(int x)
{
    long long res = ans[x] ;
    int cur = x ;
    while(cur)
    {
        res = min(res,ans[cur] + dist[x][depth[cur]]) ;
        cur = par[cur] ;
    }
    return res ;
}

void Init(int N , int A[] , int B[] , int D[])
{
    n = N ;
    for(int i = 0 ; i < (N-1) ; ++i)
    {
        edges[A[i] + 1].push_back({B[i]+1,D[i]}) ;
        edges[B[i] + 1].push_back({A[i]+1,D[i]}) ;
    }
    build(1,0,0) ;
    for(int i = 1 ; i <= N ; ++i) ans[i] = INF ;
}

long long Query(int S , int X[] , int T , int Y[])
{
    for(int i = 0 ; i < S ; ++i)
    {
        update(X[i] + 1) ;
    }
    long long res = INF ;
    for(int i = 0 ; i < T ; ++i)
    {
        res = min(res,query(Y[i] + 1)) ;
    }
    while(!st.empty())
    {
        ans[st.top()] = INF ;
        st.pop() ;
    }
    return res ;
}

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