Submission #1230988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230988		giaminhha	Factories (JOI14_factories)	C++17	100 / 100	2519 ms	157312 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mpair make_pair
using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int, ll> pii;
const int mod = 2147483647;
const ll inf = 1e18 + 7;
const int N = 5e5 + 5;


int tin[N], tout[N], t = 0;
vector<pii> adj[N];
int up[N][20];
ll d[N];

void dfs(int u, int par){
    tin[u] = ++t;
    up[u][0] = par;
    for(int i = 1; i <= 18; i++){
        if(up[u][i - 1] == -1) up[u][i] = -1;
        else up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for(pii v : adj[u]){
        if(v.fi == par) continue;
        d[v.fi] = d[u] + v.se;
        dfs(v.fi, u);
    }
    tout[u] = t;
}

bool inside(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v){
    if(inside(u, v)) return u;
    if(inside(v, u)) return v;
    for(int i = 18; i >= 0; i--){
        if(up[u][i] != -1 && !inside(up[u][i], v)){
            u = up[u][i];
        }
    }
    return up[u][0];
}
ll dist(int u, int v){
    return d[u] + d[v] - 2 * d[lca(u, v)];
}
vector<pii> edge[N];
ll dp1[N], dp2[N];
void solve(int u, int par, int state){
    for(pii v : edge[u]){
        solve(v.fi, u, state);
        if(state == 1) dp1[u] = min(dp1[u], dp1[v.fi] + v.se);
        else dp2[u] = min(dp2[u], dp2[v.fi] + v.se);
    }
}
bool comp(int u, int v){
    return tin[u] < tin[v];
}

stack<int> st;
ll Query(int S, int x[], int T, int y[]){
    int sz = S + T;
    vector<int> sorted(2 * sz - 1);

    for(int i = 0; i < S; i++){
        sorted[i] = x[i];
        dp1[x[i]] = 0;
    }
    for(int i = 0; i < T; i++){
        sorted[S + i] = y[i];
        dp2[y[i]] = 0;
    }
    sort(sorted.begin(), sorted.begin() + sz, comp);
    int nwsize = 2 * sz - 1;
    for(int i = 0; i < sz - 1; i++){
        int v = lca(sorted[i], sorted[i + 1]);
        sorted[i + sz] = v;
    }

    sort(sorted.begin(), sorted.end(), comp);
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    nwsize = sorted.size();
    
    while(!st.empty()) st.pop();
    st.pu(sorted[0]);
    for(int i = 1; i < nwsize; i++){
        while(!st.empty() && !inside(st.top(), sorted[i])){
            st.pop();
        }
        edge[st.top()].pb(mpair(sorted[i], dist(st.top(), sorted[i])));
        //cout << dist(st.top(), sorted[i]) << '\n';
        st.pu(sorted[i]);
    }

    solve(sorted[0], -1, 1);
    solve(sorted[0], -1, 2);
    ll ans = inf;
    for(int i = 0; i < nwsize; i++){
        ans = min(ans, dp1[sorted[i]] + dp2[sorted[i]]);
    }
    for(int i = 0; i < nwsize; i++){
        dp1[sorted[i]] = inf; dp2[sorted[i]] = inf;
        edge[sorted[i]].clear();
    }
    return ans;
}

void Init(int n, int a[], int b[], int w[]){
    for(int i = 0; i <= n; i++){
        dp1[i] = inf;
        dp2[i] = inf;
    }
    for(int i = 0; i < n - 1; i++){
        adj[a[i]].pb(mpair(b[i], w[i]));
        adj[b[i]].pb(mpair(a[i], w[i]));
    }
    d[0] = 0;
    dfs(0, -1);
}

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