Submission #1125718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125718		ardadut	Factories (JOI14_factories)	C++20	0 / 100	8098 ms	185672 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);
    }
}

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;
    adj.resize(n);
    anc.resize(n);
    subtree_size.resize(n);
    del.resize(n,0);
    min_dist.resize(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[]){

    fill(min_dist.begin(),min_dist.end(),1e15);

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

    return ret;
}

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