Submission #1125775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125775		ardadut	Factories (JOI14_factories)	C++20	15 / 100	8093 ms	186068 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pb push_back
#define endl "\n"
    
using namespace std;
#define maxn 500005

ll n;
ll subtree_size[maxn],min_dist[maxn];
vector<pair<ll,ll>> adj[maxn],anc[maxn];
bool del[maxn];

inline ll get_subtree(ll node, ll parent){
    subtree_size[node] = 1;
    for(auto go : adj[node]){
        if(del[go.first] or go.first == parent) continue;
        subtree_size[node] += get_subtree(go.first,node);
    }
    return subtree_size[node];
}

inline ll get_centroid(ll node, ll parent, ll tree_size){
    for(auto go : adj[node]){
        if(del[go.first] or go.first == parent) continue;
        if(subtree_size[go.first] * 2 > tree_size){
            return get_centroid(go.first,node,tree_size);
        }
    }
    return node;
}

inline void get_dist(ll node,ll centroid, ll parent,ll dist){

    for(auto go : adj[node]){
        if(del[go.first] or go.first == parent) continue;
        get_dist(go.first,centroid,node,dist + go.second);
    }

    anc[node].pb({centroid,dist});
}

inline void centroid_decomp(ll centroid){
    centroid = get_centroid(centroid,-1,get_subtree(centroid,-1));

    for(auto go : adj[centroid]){
        if(del[go.first]) continue;
        get_dist(go.first,centroid,centroid,go.second);
    }

    del[centroid] = 1;

    for(auto go : adj[centroid]){
        if(del[go.first]) continue;
        centroid_decomp(go.first);
    }
}

inline void paint(ll node){
    for(auto it : anc[node]){
        min_dist[it.first] = min(min_dist[it.first], it.second);
    }
    min_dist[node] = 0;
}

inline ll query(ll node){
    ll ans = min_dist[node];
    for(auto it : anc[node]){
        ans = min(ans,min_dist[it.first] + it.second);
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;

    for(ll i = 0 ; i < n-1 ; i++){
        adj[A[i]].pb({B[i],D[i]});
        adj[B[i]].pb({A[i],D[i]});
    }

    centroid_decomp(0);

}

long long Query(int S, int X[], int T, int Y[]){

    for(ll i = 0 ; i <= n ; i++){
        min_dist[i] = 1e15;
    }

    for(ll i = 0 ; i < S ; i++){
        paint(X[i]);
    }
    ll ret = 1e15;
    for(ll i = 0 ; i < T ; i++){
        ret = min(ret,query(Y[i]));
    }

    return ret;
}

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