제출 #240016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240016		rajarshi_basu	공장들 (JOI14_factories)	C++14	0 / 100	15 ms	1152 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 = 5e3+5;
const int LOGN = 23;

int n;
// ==================== Sparse table and basic graph setup ============================
vv<ii> g[MAXN];
ll dist[MAXN];
int depth[MAXN];
//int ancestors[LOGN][MAXN];
ii minCost[LOGN][4*MAXN];
int euler[MAXN];
int tin[MAXN];
int tout[MAXN];
int T = 0;
void dfs_init_setup_lca(int node,int p = -1){
    tin[node] = T;
    tout[node] = T;
    euler[T++] = node;
    //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);
        tout[node] = T;
        euler[T++] = node;
    }
}
inline ii combine(ii a,ii b){
    if(a.ff <= b.ff)return a;
    else return b;
}

int _log[4*MAXN+1];
void calculateSparseTables(){
    _log[1] = 0;
    for (int i = 2; i <= 4*MAXN; i++)
        _log[i] = _log[i/2] + 1;
    /*
    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];
            }
        }
    }*/
    FOR(i,LOGN){
        if(i == 0){
            FOR(j,T){
                minCost[i][j] = {depth[euler[j]],euler[j]};
                //cout << depth[j] << " " << j << endl;
            }
        }else{
            int add = (1<<(i-1));
            FOR(j,T){
                int nxt = j+add;
                if(nxt >= n){
                    minCost[i][j] = minCost[i-1][j];
                }else{
                    ii a = minCost[i-1][j];
                    ii b = minCost[i-1][nxt];
                    minCost[i][j] = combine(a,b);
                }
            }
        }
    }
    //FOR(i,T)cout << euler[i] << " ";cout << endl;
    //FOR(i,n)cout << tin[i] << " " << tout[i] << endl;
}

int LCAO1(int L,int R){
    int j = _log[R - L + 1];
    ii x = combine(minCost[j][L], minCost[j][R - (1 << j) + 1]);
    //cout << R << " " << L << " " << j << " " << x.ff << " " << x.ss << endl;
    return x.ss;
}


int LCA(int a,int b){
    if(a == b)return a;
    if(tin[a] > tin[b])swap(a,b);
    if(tout[a] > tout[b])return a;

    return LCAO1(tout[a],tin[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];
int ctr = 0;
void dfs_centroid_setup(int node,int p = -1){
    ctr++;
    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);
    calculateSparseTables();
    centroidDecomp();
    //cout << ctr << endl;
    FOR(i,n)ans[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    vv<int> affectedNodes;
    //cout << "LCA: " << LCA(2,5) << " " << distance(2,5) << endl;
    FOR(i,S){
        int item = X[i];
        while(item != -1){
            affectedNodes.pb(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: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67