Submission #1037335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037335		fryingduc	Factories (JOI14_factories)	C++17	100 / 100	6409 ms	207488 KiB

factories

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

const int maxn = 5e5 + 5;
const long long inf = 1e18;
const int lg = 20;
int n, q;
vector<pair<int, int>> g[maxn];
vector<pair<int, long long>> adj[maxn];
int tin[maxn], tout[maxn], timer;
int h[maxn], up[maxn][lg + 1];
long long dep[maxn];
bool red[maxn];
bool blue[maxn];
long long ans;

int vtin[maxn], vtout[maxn];
long long vth[maxn];

struct segment_tree {
    int n;
    vector<long long> tree, lazy;
    segment_tree() {}
    segment_tree(int n) : n(n) {
        tree.resize(n * 4 + 6, 0);
        lazy.resize(n * 4 + 6, 0);
    }
    void down(int ind, int l, int r) {
        tree[ind] += lazy[ind];
        if(l != r) {
            lazy[ind * 2] += lazy[ind];
            lazy[ind * 2 + 1] += lazy[ind];
        }
        lazy[ind] = 0;
    }
    void update(int ind, int l, int r, int x, int y, long long val) {
        if(lazy[ind]) down(ind, l, r);
        if(l > y || r < x) return;
        if(x <= l and r <= y) {
            lazy[ind] = val;
            down(ind, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(ind * 2, l, mid, x, y, val);
        update(ind * 2 + 1, mid + 1, r, x, y, val);
        tree[ind] = min(tree[ind * 2], tree[ind * 2 + 1]);
    }
    long long get(int ind, int l, int r, int x, int y) {
        if(lazy[ind]) down(ind, l, r);
        if(l > y || r < x) return inf;
        if(x <= l and r <= y) return tree[ind];
        
        int mid = (l + r) / 2;
        return min(get(ind * 2, l, mid, x, y), get(ind * 2 + 1, mid + 1, r, x, y));
    }
    void update(int x, int y, long long val) {
        if(x > y) return;
        update(1, 1, n, x, y, val);
    }
    long long get(int x, int y) {
        return get(1, 1, n, x, y);
    }
    long long get() {
        return get(1, 1, n, 1, n);
    }
} t;

void dfs(int u, int prev) {
    tin[u] = ++timer;
    for(auto e:g[u]) {
        if(e.first == prev) continue;
        h[e.first] = h[u] + 1;
        dep[e.first] = dep[u] + e.second;
        up[e.first][0] = u;
        dfs(e.first, u);
    }
    tout[u] = timer;
}
bool is_anc(int u, int v) {
    return tin[u] <= tin[v] and tout[v] <= tout[u];
}
int lca(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    int depth = h[u] - h[v];
    for(int i = lg; i >= 0; --i) {
        if(depth >> i & 1) u = up[u][i];
    }
    if(u == v) return u;
    for(int i = lg; i >= 0; --i) {
        if(up[u][i] != up[v][i]) {
            u = up[u][i], v = up[v][i];
        }
    }
    return up[u][0];
}
long long dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void vt_dfs(int u, int prev) {
    vtin[u] = ++timer;
    
    if(blue[u]) t.update(vtin[u], vtin[u], vth[u]);
    else t.update(vtin[u], vtin[u], inf);
    
    for(auto e:adj[u]) {
        int v = e.first;
        long long w = e.second;
        if(v == prev) continue;
        vth[v] = vth[u] + w;
        
        vt_dfs(v, u);
    }
    vtout[u] = timer;
}
void update(int u, long long val) {
    t.update(vtin[u], vtout[u], -val);
    t.update(1, vtin[u] - 1, val);
    t.update(vtout[u] + 1, timer, val);
}
void reroot(int u, int prev) {
    if(red[u]) {
        ans = min(ans, t.get());
//        cout << t.get() << '\n';
    }
    for(auto e:adj[u]) {
        int v = e.first;
        long long w = e.second;
        if(v == prev) continue;
        
        update(v, w);
        reroot(v, u);
        update(v, -w);
    }
}
long long virtual_tree(vector<int> &ver) {
    for(auto &i:ver) ++i;
    sort(ver.begin(), ver.end(), [](const int &x, const int &y) -> bool {
        return tin[x] < tin[y];
    });
    ver.erase(unique(ver.begin(), ver.end()), ver.end());
    int cur_sz = (int)ver.size();
    for(int i = 1; i < cur_sz; ++i) {
        ver.push_back(lca(ver[i], ver[i - 1]));
    }
    sort(ver.begin(), ver.end(), [](const int &x, const int &y) -> bool {
        return tin[x] < tin[y];
    });
    ver.erase(unique(ver.begin(), ver.end()), ver.end());
    
    stack<int> st; 
    st.push(ver[0]);
    for(int i = 1; i < (int)ver.size(); ++i) {
        while(!st.empty() and !is_anc(st.top(), ver[i])) st.pop();
        
        if(!st.empty()) {
            int u = st.top(), v = ver[i];
            long long w = dist(u, v);
            
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
        st.push(ver[i]);        
    }
    
    t = segment_tree((int)ver.size());
    timer = 0;
    vt_dfs(ver[0], 0);
    ans = inf;
    reroot(ver[0], 0);
    
    for(auto u:ver) {
        red[u] = blue[u] = 0;
        vth[u] = 0;
        adj[u].clear();
    }
    return ans;
}
void Init(int _n, int a[], int b[], int d[]) {
    n = _n;
    for(int i = 0; i < n - 1; ++i) {
        int u = a[i], v = b[i], w = d[i];
        ++u, ++v;
        
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    
    dfs(1, 0);
    for(int i = 1; i <= lg; ++i) {
        for(int u = 1; u <= n; ++u) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
    }
}
long long Query(int s, int x[], int t, int y[]) {
    vector<int> ver;
    for(int i = 0; i < s; ++i) {
        ver.push_back(x[i]);
        red[x[i] + 1] = 1;
    }
    for(int i = 0; i < t; ++i) {
        ver.push_back(y[i]);
        
        blue[y[i] + 1] = 1;
    }
    
    return virtual_tree(ver);
}

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