Submission #1271180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271180		leanderson	Factories (JOI14_factories)	C++20	100 / 100	4726 ms	328928 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const ll MAXN = 5e5+50;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define optimize ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"

vector<vector<pair<int,int>>> g_adj(MAXN);
vector <int> sub(MAXN);
vector <bool> removed(MAXN);
vector<pair<int,ll>> dists_to_ancestor[MAXN]; // (centroid, distance)

int n,k1,k2;
ll answer = 0;

void dfs_store_distances(int u, int p, ll current_distance, int centroid){
    dists_to_ancestor[u].push_back({centroid, current_distance});
    for (auto &edge : g_adj[u]){
        int v = edge.first;
        int weight = edge.second;
        if (v == p || removed[v]) continue;
        dfs_store_distances(v, u, current_distance + weight, centroid);
    }
}

int dfs_size(int u, int p){
    sub[u] = 1;
    for (auto &edge : g_adj[u]){
        int v = edge.first;
        if (v == p || removed[v]) continue;
        sub[u] += dfs_size(v, u);
    }
    return sub[u];
}
int dfs_find_centroid(int u, int p, int n){
    for (auto &edge : g_adj[u]){
        int v = edge.first;
        if (v == p || removed[v]) continue;
        if (sub[v] > n/2) return dfs_find_centroid(v, u, n);
    }
    return u;
}
void decompose(int start){
    int n_comp = dfs_size(start, -1);
    int centroid = dfs_find_centroid(start, -1, n_comp);

    dfs_store_distances(centroid, -1, 0, centroid); // Store distances to this centroid

    removed[centroid] = true;
    for (auto &edge : g_adj[centroid]){
        int v = edge.first;
        if (!removed[v]) decompose(v);
    }
}
long long Query(int S, int X[], int T, int Y[]){

    unordered_map<int,ll> dist_to_y;

    for (int i=0;i<T;i++){
        int node = Y[i];

        for (auto &pr :dists_to_ancestor[node]){
            int centroid = pr.first;
            ll distance = pr.second;
            if (dist_to_y.find(centroid) == dist_to_y.end()){
                dist_to_y[centroid] = distance;
            } else {
                dist_to_y[centroid] = min(dist_to_y[centroid], distance);
            }
        }
    }

    ll min_distance = INFLL;

    for (int i=0;i<S;i++){
        int node = X[i];

        for (auto &pr :dists_to_ancestor[node]){
            int centroid_ancestor = pr.first;
            ll distance_to_ancestor = pr.second;
            if (dist_to_y.find(centroid_ancestor) != dist_to_y.end()){
                ll total_distance = distance_to_ancestor + dist_to_y[centroid_ancestor];
                min_distance = min(min_distance, total_distance);
            }
        
        }    
    }
    if (min_distance == INFLL) return -1;
    return min_distance;
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i=0;i<n-1;i++){
        int u = A[i];
        int v = B[i];
        int w = D[i];
        g_adj[u].push_back({v,w});
        g_adj[v].push_back({u,w});
    }

    decompose(0);
}
/*
void solve(){
    cin >> n >> k1 >> k2;
    

    for (int i=0; i<n-1; i++){
        int u,v;
        cin >> u >> v;
        --u; --v; 
        g_adj[u].push_back(v);
        g_adj[v].push_back(u);
    }

    decompose(0);
    
    cout << answer << endl;
}

int main (){
    optimize;
    solve();
    return 0;
}
    */

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