Submission #495566

#	Time	Username	Problem	Language	Result	Execution time	Memory
495566		K4YAN	Factories (JOI14_factories)	C++17	0 / 100	249 ms	524292 KiB

factories

//Be Name Khoda

#include<bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>

const ll mxn = 5e5 + 16, INF = 1e15 + 32;
ll n, m, q, w, ans;
ll st[mxn], fn[mxn], h[mxn], dis[mxn], c[mxn], dp[mxn][3], par[mxn][20];
vector<ll> f, g;
vector<pll> adj[mxn], G[mxn];
set<ll> s;
bitset<mxn> mark;

void DFS(int v) {

    mark.set(v);
    st[v] = q++, fn[v] = q, h[v] = w++;
    for(int i = 1; i < 20; i++) {
        par[v][i] = par[par[v][i - 1]][i - 1];
    }
    for(auto u : adj[v]) {
        if(!mark[u.first]) {
            par[u.first][0] = v;
            dis[u.first] = h[v] + u.second;
            DFS(u.first);
            fn[v] = fn[u.first];
        }
    } w--;

}

void Init(int N, int A[], int B[], int D[]) {

    n = N;
    for(int i = 0; i < n - 1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    DFS(0);
    mark.reset();

}

inline void clr() {
    for(auto u : f) {
        c[u] = 0;
    } f.clear(); 
    return;
}

bool comp(int a, int b) {
    return st[a] < st[b];
}

ll find_lca(ll v, ll u) {
    if(v == u) return v;
    if(h[v] > h[u]) {
        swap(v, u);
    }
    for(int i = 19; i > -1; i--) {
        if(h[u] - (1LL << i) < h[v]) continue;
        u = par[u][i];
    }
    if(v == u) return v;
    for(int i = 19; i > -1; i--) {
        if(par[u][i] != par[v][i]) {
            u = par[u][i], v = par[v][i];
        }
    } return par[v][0];
}

inline void build_Graph() {
    stack<ll> st;
    st.push(g[0]); dp[g[0]][0] = dp[g[0]][1] = dp[g[0]][2] = INF;
    for(int i = 1; i < int(g.size()); i++) {
        while(fn[st.top()] < fn[f[i]]) st.pop();
        dp[g[i]][0] = dp[g[i]][1] = dp[g[i]][2] = INF;
        G[st.top()].push_back({f[i], dis[f[i]] - dis[st.top()]});
        st.push(f[i]);
    }
}

void solve_dp(int v) {

    dp[v][c[v] % 2] = 0;
    for(auto u : G[v]) {
        solve_dp(u.first);
        dp[v][2] = min(dp[v][2], dp[u.first][2]);
        dp[v][1] = min(dp[v][1], dp[u.first][1] + u.second);
        dp[v][0] = min(dp[v][0], dp[u.first][0] + u.second);
    }
    dp[v][2] = min(dp[v][2], dp[v][1] + dp[v][0]);
    return;

}

ll Query(int S, int X[], int T, int Y[]) {

    for(auto u : g) {
        G[u].clear();
    } clr(); s.clear(), f.clear(), g.clear();

    for(int i = 0; i < S; i++) {
        c[X[i]] = 1; f.push_back(X[i]); s.insert(X[i]);
    } for(int i = 0; i < T; i++) {
        c[Y[i]] += 2;
        f.push_back(Y[i]); s.insert(Y[i]);
        if(c[Y[i]] == 3) {
            return 0;
        }
    }
    sort(all(f), comp);
    g = f;
    for(int i = 0; i < int(f.size()) - 1; i++) {
        w = find_lca(f[i], f[i + 1]);
        if(!s.count(w)) {
            s.insert(w);
            g.push_back(w);
        }
    }
    sort(all(g), comp);
    build_Graph();
    solve_dp(g[0]);
    ans = dp[g[0]][2];
    return ans;

}

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