Submission #1292622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292622		Minbaev	Factories (JOI14_factories)	C++20	0 / 100	21 ms	788 KiB

factories

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

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 val){
        tree[v] = val * (r - l + 1);
        lazy[v] = val;
    }
    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 val){
        if(ql>qr || r<ql || qr<l) return;
        if(ql<=l && r<=qr){ apply(v,l,r,val); return; }
        push(v,l,r);
        int m=(l+r)>>1;
        upd(v<<1,l,m,ql,qr,val);
        upd(v<<1|1,m+1,r,ql,qr,val);
        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);
    }
    void range_assign(int l,int r,int val){ if(l>r) return; upd(1,1,n,l,r,(ll)val); }
    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> parent_v, sz_v, idv, id_rev, head;
static vector<ll> dep;
static int timer_;
static Seg seg;

void dfs(int u,int p){
    parent_v[u]=p;
    sz_v[u]=1;
    for(auto &e: g[u]){
        int v=e.first, w=e.second;
        if(v==p) continue;
        dep[v]=dep[u]+(ll)w;
        dfs(v,u);
        sz_v[u]+=sz_v[v];
    }
}

void hld(int u,int p){
    int heavy=-1;
    for(auto &e: g[u]){
        int v=e.first;
        if(v==p) continue;
        if(heavy==-1 || sz_v[v]>sz_v[heavy]) heavy=v;
    }
    timer_++;
    idv[u]=timer_;
    id_rev[timer_]=u;
    if(heavy!=-1){
        head[heavy]=head[u];
        hld(heavy,u);
    }
    for(auto &e: g[u]){
        int v=e.first;
        if(v==p || v==heavy) continue;
        head[v]=v;
        hld(v,u);
    }
}

int up_node(int x){
    while(true){
        int h=head[x];
        int hid=idv[h], xid=idv[x];
        if(hid+1 <= xid){
            ll ones = seg.range_sum(hid+1, xid);
            ll need = (ll)(xid - hid);
            if(ones == need){
                if(parent_v[h]==-1) return h;
                x = parent_v[h];
                continue;
            } else {
                int L = hid+1, R = xid;
                while(L < R){
                    int M = (L + R) >> 1;
                    ll s = seg.range_sum(M, xid);
                    ll need2 = (ll)(xid - M + 1);
                    if(s == need2) R = M;
                    else L = M + 1;
                }
                int topnode = id_rev[L-1];
                return topnode;
            }
        } else {
            if(parent_v[h]==-1) return h;
            x = parent_v[h];
            continue;
        }
    }
}

void set_path_up(int x,int val){
    while(true){
        int h=head[x];
        int hid=idv[h], xid=idv[x];
        if(hid+1 <= xid) seg.range_assign(hid+1, xid, val);
        if(parent_v[h]==-1) break;
        x = parent_v[h];
    }
}

void Init(int N, int A[], int B[], int D[]){
    Nglob = N;
    g.assign(Nglob, {});
    parent_v.assign(Nglob, -1);
    sz_v.assign(Nglob, 0);
    idv.assign(Nglob, 0);
    id_rev.assign(Nglob+1, 0);
    head.assign(Nglob, 0);
    dep.assign(Nglob, 0);
    timer_ = 0;
    for(int i=0;i<Nglob-1;i++){
        int a=A[i], b=B[i], d=D[i];
        g[a].push_back({b,d});
        g[b].push_back({a,d});
    }
    dep[0]=0;
    dfs(0,-1);
    head[0]=0;
    hld(0,-1);
    seg.init(Nglob);
}

long long Query(int S, int X[], int T, int Y[]){
    for(int i=0;i<S;i++) set_path_up(X[i], 1);
    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);
    }
    for(int i=0;i<S;i++) set_path_up(X[i], 0);
    unordered_map<int,ll> best;
    best.reserve(vs.size()*2+3);
    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;
    }
    for(auto &kv: best){
        int u = kv.first;
        ll val = kv.second;
        seg.range_assign(idv[u], idv[u], (int)val);
    }
    ll ans = LLONG_MAX;
    for(int i=0;i<S;i++){
        int x = X[i];
        int u = up_node(x);
        ll cell = seg.range_sum(idv[u], idv[u]);
        if(cell==0) continue;
        ll cand = (dep[x] - dep[u]) + cell;
        if(cand < ans) ans = cand;
    }
    for(auto &kv: best){
        seg.range_assign(idv[kv.first], idv[kv.first], 0);
    }
    if(ans==LLONG_MAX) return -1;
    return ans;
}

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