Submission #239783

#	Time	Username	Problem	Language	Result	Execution time	Memory
239783		rajarshi_basu	Factories (JOI14_factories)	C++14	15 / 100	5410 ms	40828 KiB

factories

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#include <stdio.h>     
#include <stdlib.h>    
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include "factories.h"
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
#define ld long double
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define il pair<int,ll>
#define ii pair<int,int>
#define lii pair<pair<ll,int>,il>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define vv vector
#define endl '\n'
 
using namespace std;

const ll INF = 1e17;
const int MAXN = 2e5;
const int LOGN = 20;

int n;
// ==================== Sparse table and basic graph setup ============================
vv<ii> g[MAXN];
ll dist[MAXN];
int depth[MAXN];
int ancestors[LOGN][MAXN];
void dfs_init_setup_lca(int node,int p = -1){
    ancestors[0][node] = p;
    for(auto e: g[node]){
        if(e.ff == p)continue;
        dist[e.ff] = e.ss + dist[node];
        depth[e.ff] = 1+ depth[node];
        dfs_init_setup_lca(e.ff,node);
    }
}
void calculateSparseTable(){
    FOR(i,LOGN){
        if(i > 0){
            FOR(j,n){
                int p = ancestors[i-1][j];
                if(p == -1)ancestors[i][j] = -1;
                else ancestors[i][j] = ancestors[i-1][p];
            }
        }
    }
}
int LCA(int a,int b){
    if(depth[a] < depth[b])swap(a,b);
    FOR(i,LOGN){
        int j = LOGN-i-1;
        if(depth[ancestors[j][a]] >= depth[b])a = ancestors[j][a];
    }
    if(a == b)return a;
    FOR(i,LOGN){
        int j = LOGN - i -1;
        if(ancestors[j][a] != ancestors[j][b])
            a = ancestors[j][a],
            b = ancestors[j][b];
    }
    return ancestors[0][a];
}
ll distance(int a,int b){
    return dist[a] + dist[b] - 2*dist[LCA(a,b)];
}
// ==================== Centroid tree construction ====================================
bool blocked[MAXN];
int subtree[MAXN];
int centroidParent[MAXN];
void dfs_centroid_setup(int node,int p = -1){
    subtree[node] = 1;
    for(auto e: g[node]){
        if(blocked[e.ff] or e.ff == p)continue;
        dfs_centroid_setup(e.ff,node);
        subtree[node] += subtree[e.ff];
    }
}
int getCentroid(int node,int tot,int p = -1){
    for(auto e: g[node]){
        if(blocked[e.ff] or e.ff == p)continue;
        if(2*subtree[e.ff] > tot)return getCentroid(e.ff,tot,node); 
    }
    return node;
}
queue<ii> subtrees_remaining;
void processCentroid(int node,int par){
    dfs_centroid_setup(node);
    int c = getCentroid(node,subtree[node]);
    centroidParent[c] = par;
    for(auto e: g[c]){
        if(blocked[e.ff])continue;
        subtrees_remaining.push({e.ff,c});
    }
    blocked[c] = 1;
}

void centroidDecomp(){
    subtrees_remaining.push({0,-1});
    while(!subtrees_remaining.empty()){
        auto e = subtrees_remaining.front();subtrees_remaining.pop();
        processCentroid(e.ff,e.ss);
    }
}
// ==================== Problem Specific Stuff =======================================
ll ans[MAXN];


void Init(int n, int A[], int B[], int D[]) {
    ::n = n;
    FOR(i,n-1){
        g[A[i]].pb({B[i],D[i]});
        g[B[i]].pb({A[i],D[i]});
    }
    dfs_init_setup_lca(0);
    calculateSparseTable();
    centroidDecomp();
    FOR(i,n)ans[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    set<int> affectedNodes;
    //cout << "LCA: " << LCA(2,5) << " " << distance(2,5) << endl;
    FOR(i,S){
        int item = X[i];
        while(item != -1){
            affectedNodes.insert(item);
            ans[item] = min(ans[item],distance(item,X[i]));
            item = centroidParent[item];
        }
    }
    ll d = INF;
    FOR(i,T){
        int item = Y[i];
        while(item != -1){
            d = min(d,distance(item,Y[i])+ans[item]);
            item = centroidParent[item];
        }
    }
    for(auto e: affectedNodes)ans[e] = INF;
    return d;
}

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