Submission #425617

#	Time	Username	Problem	Language	Result	Execution time	Memory
425617		kostia244	Factories (JOI14_factories)	C++17	100 / 100	4655 ms	141548 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int N = 5e5 + 12;
int n, sz[N], head[N], p[N];
ll dep[N];
vector<array<int, 2>> g[N];
struct MNode { ll a = 1ll<<55; 
    MNode() {}
    MNode(ll x) : a(x) {}
    friend MNode operator+(const MNode &a, const MNode &b) {
        return MNode(min(a.a, b.a));
    }
};
template<class Node>
struct SegTree {
    int n;
    vector<Node> tree;
    SegTree(int N) : n(N), tree(2*n) {}
    void upd(int pos, Node val) {
        for(tree[pos+=n]=val;pos/=2;)
            tree[pos] = tree[2*pos]+tree[2*pos+1];
    }
    Node query(int l, int r) {
        Node res;
        for(l += n, r += n; l < r; l>>=1,r>>=1) {
            if(l&1) res = res + tree[l++];
            if(r&1) res = tree[--r] + res;
        }
        return res;
    }
};
int tin[N], tout[N], timer = 0;
void sizes(int v) {
    sz[v] = 1;
    for(auto &F : g[v]) {
        auto i = F[0];
        auto w = F[1];
        p[i] = v;
        dep[i] = dep[v]+w;
        g[i].erase(find(all(g[i]), array<int, 2>{v, w}));
        sizes(i);
        sz[v] += sz[i];
        if(sz[i] > sz[g[v][0][0]])
            swap(g[v][0], F);
    }
}
void hld(int v) {
    tin[v] = timer++;
    for(auto &[i, w] : g[v]) {
        head[i] = i == g[v][0][0] ? head[v] : i;
        hld(i);
    }
    tout[v] = timer;
}
SegTree<MNode> st(0);
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    st = SegTree<MNode>(n);
    for(int i = 0; i+1 < n; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    sizes(0);
    hld(0);
}

template<int undo>
void update(int v) {
    st.upd(tin[v], undo ? MNode() : MNode(dep[v]));
    //cout << tin[v] << " _ " << dep[v] << " " << st.query(0, n).a << endl;
}
void query(int v, ll &ans) {
    ll md = dep[v];
    while(true) {
        ans = min(ans, st.query(tin[v], tout[v]).a+md-2*dep[v]);
        if(!v) break;
        v = p[head[v]];
    }
}

void solve(int s, int x[], int t, int y[], ll &ans) {
    for(int i = 0; i < s; i++)
        update<0>(x[i]);
    //cout << "F " << tin[0] << " " << tout[0] << endl;
    for(int i = 0; i < t; i++)
        query(y[i], ans);
    for(int i = 0; i < s; i++)
        update<1>(x[i]);
}

long long Query(int s, int x[], int t, int y[]) {
    ll ans = 1ll<<60;
    solve(s, x, t, y, ans);
    solve(t, y, s, x, ans);
    return ans;
}

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