oj.uz

Submission #360182

# Submission time Handle Problem Language Result Execution time Memory
360182 2021-01-27T16:20:34 Z shahriarkhan Factories (JOI14_factories) C++14
15 / 100
 8000 ms 170752 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63596 KB Output is correct
2 Correct 1164 ms 81388 KB Output is correct
3 Correct 2025 ms 81692 KB Output is correct
4 Correct 1988 ms 81524 KB Output is correct
5 Correct 2444 ms 81836 KB Output is correct
6 Correct 468 ms 81260 KB Output is correct
7 Correct 2003 ms 81372 KB Output is correct
8 Correct 2119 ms 81616 KB Output is correct
9 Correct 2376 ms 81740 KB Output is correct
10 Correct 454 ms 81388 KB Output is correct
11 Correct 2053 ms 81436 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63212 KB Output is correct
2 Correct 3807 ms 170752 KB Output is correct
3 Execution timed out 8077 ms 169084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63596 KB Output is correct
2 Correct 1164 ms 81388 KB Output is correct
3 Correct 2025 ms 81692 KB Output is correct
4 Correct 1988 ms 81524 KB Output is correct
5 Correct 2444 ms 81836 KB Output is correct
6 Correct 468 ms 81260 KB Output is correct
7 Correct 2003 ms 81372 KB Output is correct
8 Correct 2119 ms 81616 KB Output is correct
9 Correct 2376 ms 81740 KB Output is correct
10 Correct 454 ms 81388 KB Output is correct
11 Correct 2053 ms 81436 KB Output is correct
12 Correct 39 ms 63212 KB Output is correct
13 Correct 3807 ms 170752 KB Output is correct
14 Execution timed out 8077 ms 169084 KB Time limit exceeded
15 Halted 0 ms 0 KB -