Submission #1125798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125798		ardadut	Factories (JOI14_factories)	C++20	100 / 100	5000 ms	316064 KiB

factories

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

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

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);
    }
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    adj.resize(n);
    anc.resize(n);
    subtree_size.resize(n);
    del.resize(n,0);
    min_dist.resize(n,1e15);

    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 < S ; i++){
        for(auto it : anc[X[i]]){
            min_dist[it.first] = min(min_dist[it.first], it.second);
        }
        min_dist[X[i]] = 0;
    }

    ll ret = 1e15;

    for(ll i = 0 ; i < T ; i++){
        ret = min(ret,min_dist[Y[i]]);
        for(auto it : anc[Y[i]]){
            ret = min(ret,min_dist[it.first] + it.second);
        }
    }

    for(ll i = 0 ; i < S ; i++){
        for(auto it : anc[X[i]]){
            min_dist[it.first] = 1e15;
        }
        min_dist[X[i]] = 1e15;
    }

    return ret;
}

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