Submission #360182

#	Time	Username	Problem	Language	Result	Execution time	Memory
360182		shahriarkhan	Factories (JOI14_factories)	C++14	15 / 100	8077 ms	170752 KiB

factories

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

const int LG = 20 , mx = 5e5 + 10 ;

const long long INF = 1e18 ;

set<pair<int,long long> > g[mx] ;

int n , m , p[mx][LG] , depth[mx] , siz[mx] , parent[mx] ;
long long ans[mx] , cost[mx] ;

void dfs(int u , int par , int deep = 0 , long long cst = 0)
{
    depth[u] = deep , cost[u] = cst , p[u][0] = par ;
    for(pair<int,long long> v : g[u])
    {
        if(v.first==par) continue ;
        dfs(v.first,u,deep+1,cst+v.second) ;
    }
}

int comp ;

void visit(int u , int par)
{
    ++comp , siz[u] = 1;
    for(pair<int,long long> v : g[u])
    {
        if(v.first==par) continue ;
        visit(v.first,u) ;
        siz[u] += siz[v.first] ;
    }
}

int find_centroid(int u , int par)
{
    for(pair<int,long long> v : g[u])
    {
        if(v.first==par) continue ;
        if(siz[v.first] > (comp/2))
        {
            return find_centroid(v.first,u) ;
        }
    }
    return u ;
}

void decompose(int u , int par)
{
    comp = 0 , visit(u,u) ;
    int centroid = find_centroid(u,u) ;
    parent[centroid] = par ;
    for(pair<int,long long> v : g[centroid])
    {
        g[v.first].erase({centroid,v.second}) ;
        decompose(v.first,centroid) ;
    }
    g[centroid].clear() ;
}

int lca(int u , int v)
{
    if(depth[u] < depth[v]) swap(u,v) ;
    for(int i = LG - 1 ; i >= 0 ; --i)
    {
        if((depth[u] - (1<<i))>=depth[v]) u = p[u][i] ;
    }
    if(u==v) return u ;
    for(int i = LG - 1 ; i >= 0 ; --i)
    {
        if(p[u][i] != -1 && p[u][i] != p[v][i])
        {
            u = p[u][i] , v = p[v][i] ;
        }
    }
    return p[u][0] ;
}

long long dist(int u , int v)
{
    return cost[u] + cost[v] - 2*cost[lca(u,v)] ;
}

void update(int u)
{
    int x = u ;
    while(1)
    {
        ans[x] = min(ans[x],dist(x,u)) ;
        if(parent[x]==x || parent[x] == -1) break ;
        x = parent[x] ;
    }
}

void clean(int u)
{
    int x = u ;
    while(1)
    {
        ans[x] = INF ;
        if(parent[x]==x || parent[x] == -1) break ;
        x = parent[x] ;
    }
}

long long query(int u)
{
    int x = u ;
    long long res = INF ;
    while(1)
    {
        res = min(res,ans[x] + dist(x,u)) ;
        if(parent[x]==x || parent[x] == -1) break ;
        x = parent[x] ;
    }
    return res ;
}

void Init(int N , int A[] , int B[] , int D[])
{
    n = N ;
    for(int i = 0 ; i < (N-1) ; ++i)
    {
        g[A[i]].insert({B[i],D[i]}) ;
        g[B[i]].insert({A[i],D[i]}) ;
    }
    memset(p,-1,sizeof(p)) ;
    dfs(0,0) ;
    decompose(0,-1) ;
    for(int j = 1 ; j < LG ; ++j)
    {
        for(int i = 0 ; i < n ; ++i)
        {
            if(p[i][j-1] != -1)
            {
                p[i][j] = p[p[i][j-1]][j-1] ;
            }
        }
    }
    for(int i = 0 ; i < n ; ++i) ans[i] = INF ;
}

long long Query(int S , int X[] , int T , int Y[])
{
    long long res = INF ;
    for(int i = 0 ; i < S ; ++i) update(X[i]) ;
    for(int i = 0 ; i < T ; ++i)
    {
        res = min(res,query(Y[i])) ;
    }
    for(int i = 0 ; i < S ; ++i) clean(X[i]) ;
    return res ;
}

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