제출 #1292607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292607		Minbaev	공장들 (JOI14_factories)	C++20	0 / 100	19 ms	792 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define ar array

struct Seg {
    int n;
    vector<ll> tree, lazy;
    Seg() : n(0) {}
    Seg(int _n) { init(_n); }
    void init(int _n){
        n = _n;
        tree.assign(4*n+5, 0);
        lazy.assign(4*n+5, LLONG_MAX);
    }
    inline void apply(int v, int l, int r, ll x){
        tree[v] = x * (r - l + 1);
        lazy[v] = x;
    }
    inline void push(int v, int l, int r){
        if(lazy[v] == LLONG_MAX) return;
        if(l != r){
            int m = (l + r) >> 1;
            apply(v<<1, l, m, lazy[v]);
            apply(v<<1|1, m+1, r, lazy[v]);
        }
        lazy[v] = LLONG_MAX;
    }
    void upd(int v, int l, int r, int ql, int qr, ll x){
        if(ql > qr || r < ql || qr < l) return;
        if(ql <= l && r <= qr){
            apply(v, l, r, x);
            return;
        }
        push(v, l, r);
        int m = (l + r) >> 1;
        upd(v<<1, l, m, ql, qr, x);
        upd(v<<1|1, m+1, r, ql, qr, x);
        tree[v] = tree[v<<1] + tree[v<<1|1];
    }
    ll get(int v, int l, int r, int ql, int qr){
        if(ql > qr || r < ql || qr < l) return 0;
        if(ql <= l && r <= qr){
            return tree[v];
        }
        push(v, l, r);
        int m = (l + r) >> 1;
        return get(v<<1, l, m, ql, qr) + get(v<<1|1, m+1, r, ql, qr);
    }

    // helpers
    void range_assign(int l, int r, ll x){
        if(l>r) return;
        upd(1,1,n,l,r,x);
    }
    ll range_sum(int l, int r){
        if(l>r) return 0;
        return get(1,1,n,l,r);
    }
};

static int Nglob = 0;
static vector<vector<pair<int,int>>> g;
static vector<int> id_, id_rev, head, parent_, sz;
static vector<ll> dep;
static int timer_;
static Seg seg;

void dfs_hld(int u, int p){
    parent_[u] = p;
    sz[u] = 1;
    for(auto &ed : g[u]){
        int v = ed.first; int w = ed.second;
        if(v == p) continue;
        dep[v] = dep[u] + (ll)w;
        dfs_hld(v, u);
        sz[u] += sz[v];
    }
}

void hld_build(int u, int p){
    int heavy = -1;
    for(auto &ed : g[u]){
        int v = ed.first;
        if(v == p) continue;
        if(heavy == -1 || sz[v] > sz[heavy]) heavy = v;
    }
    // assign id
    timer_++;
    id_[u] = timer_;
    id_rev[timer_] = u;

    if(heavy != -1){
        head[heavy] = head[u];
        hld_build(heavy, u);
    }
    for(auto &ed : g[u]){
        int v = ed.first;
        if(v == p || v == heavy) continue;
        head[v] = v;
        hld_build(v, u);
    }
}

// helper: sum of enabled edges on chain head..x
// note: edges are represented by positions id[node]; the edge parent->node sits at id[node] (root has no edge)
inline ll chain_sum_edges(int h_id, int x_id){
    // edges on path from node with id h_id to node with id x_id are positions (h_id+1 .. x_id)
    if(h_id + 1 > x_id) return 0;
    return seg.range_sum(h_id + 1, x_id);
}

// up(x): find top-most node of the component containing x when edges marked =1
int up_node(int x){
    // if the node itself has no edges upward (i.e., path empty), we may return it
    while(true){
        int h = head[x];
        int hid = id_[h];
        int xid = id_[x];
        ll total = chain_sum_edges(hid, xid);
        if(total == (ll)(xid - hid)){
            // whole chain from h..x is filled; try go above
            if(parent_[h] == -1) return h;
            x = parent_[h];
            continue;
        } else {
            // binary search within [hid, xid] to find minimal pos pos such that edges pos+1..xid are all ones
            int L = hid, R = xid;
            while(L < R){
                int M = (L + R) >> 1;
                ll s = chain_sum_edges(M, xid);
                if(s == (ll)(xid - M)) R = M;
                else L = M + 1;
            }
            return id_rev[L];
        }
    }
}

// set all edges on path from root of chain to node x to value val (0 or 1)
void set_path_up(int x, int val){
    while(true){
        int h = head[x];
        int hid = id_[h];
        int xid = id_[x];
        if(hid + 1 <= xid) seg.range_assign(hid+1, xid, val);
        if(parent_[h] == -1) break;
        x = parent_[h];
    }
}

// API functions required by grader
void Init(int N, int A[], int B[], int D[]){
    Nglob = N;
    g.clear(); g.resize(Nglob);
    id_.assign(Nglob, 0);
    id_rev.assign(Nglob+1, 0); // 1-based ids -> id_rev[1..N]
    head.assign(Nglob, 0);
    parent_.assign(Nglob, -1);
    sz.assign(Nglob, 0);
    dep.assign(Nglob, 0);
    timer_ = 0;

    // A,B,D length N-1
    for(int i = 0; i < Nglob - 1; ++i){
        int a = A[i], b = B[i], d = D[i];
        // assume input nodes are 0-based as in JOI spec
        g[a].push_back({b, d});
        g[b].push_back({a, d});
    }

    // root at 0
    dep[0] = 0;
    parent_[0] = -1;
    dfs_hld(0, -1);
    head[0] = 0;
    hld_build(0, -1);

    // seg tree size = N (we use positions 1..N)
    seg.init(Nglob);
}

long long Query(int S, int X[], int T, int Y[]){
    // mark all chains from each X[i] to top (set edges = 1)
    for(int i = 0; i < S; ++i){
        int v = X[i];
        set_path_up(v, 1);
    }

    // for each Y find its top-most node u and distance from Y to u
    vector<pair<int,ll>> vs;
    vs.reserve(T);
    for(int i = 0; i < T; ++i){
        int y = Y[i];
        int u = up_node(y);
        ll dist = dep[y] - dep[u];
        vs.emplace_back(u, dist);
    }

    // unmark X chains (restore edges = 0)
    for(int i = 0; i < S; ++i){
        int v = X[i];
        set_path_up(v, 0);
    }

    // reduce vs to minimal per u
    unordered_map<int,ll> best;
    best.reserve(vs.size()*2+5);
    for(auto &pr : vs){
        int u = pr.first;
        ll d = pr.second;
        auto it = best.find(u);
        if(it == best.end()) best[u] = d;
        else if(d < it->second) it->second = d;
    }

    ll ans = LLONG_MAX;
    for(int i = 0; i < S; ++i){
        int x = X[i];
        int u = up_node(x);
        auto it = best.find(u);
        if(it == best.end()) continue;
        ll cand = (dep[x] - dep[u]) + it->second;
        if(cand < ans) ans = cand;
    }

    if(ans == LLONG_MAX) return -1; // if unreachable; problem statement may guarantee reachable, adapt if needed
    return ans;
}

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