Submission #1065207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065207		Boycl07	Factories (JOI14_factories)	C++17	100 / 100	1800 ms	171092 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "note"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)
 
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
 
const int Max_N = 5e5 + 3;
const int LOG =  18;
const ll INF = 1e18;
int up[Max_N][LOG + 1], tin[Max_N], tout[Max_N], timedfs = 0;
 
int n;
vector<pii> g[Max_N];
 
ll dist[Max_N];
ll dp[Max_N][2];
 
 
void dfs(int u, int p)
{
    tin[u] = ++timedfs;
    up[u][0] = p;
 
    forn(j, 1, LOG) up[u][j] = up[up[u][j - 1]][j - 1];
 
    for(auto &[v, w] : g[u])
        if(v != p) dist[v] = dist[u] + w, dfs(v, u);
    
    tout[u] = timedfs;
}
 
bool is_anc(int u, int v) {return tin[u] <= tin[v] && tout[v] <= tout[u];}
 
int lca(int u, int v)
{
    if(is_anc(u, v)) return u;
    if(is_anc(v, u)) return v;
    ford(i, LOG, 0) if(!is_anc(up[u][i], v)) u = up[u][i];
    return up[u][0];
}
 
void Init(int N, int A[], int B[], int C[])
{
    n = N;
    FOR(i, N - 1)
    {
        g[A[i]].pb({B[i], C[i]});
        g[B[i]].pb({A[i], C[i]});
    }
    forn(i, 0, n - 1) dp[i][0] = dp[i][1] = INF;
    dfs(0, 0);
 
}
int tree[Max_N];
vector<int> adj[Max_N];
 
ll Query(int S, int X[], int T, int Y[])
{
    int cur = 0;
    FOR(i, S) tree[++cur] = X[i], dp[X[i]][0] = dist[X[i]];
    FOR(i, T) tree[++cur] = Y[i], dp[Y[i]][1] = dist[Y[i]];
    sort(tree + 1, tree + 1 + cur, [&](const int &x, const int &y) {
        return tin[x] < tin[y];
    });
    for(int i = cur - 1; i >= 1; --i) tree[++cur] = lca(tree[i], tree[i + 1]);
    sort(tree + 1, tree + 1 + cur, [&](const int &x, const int &y) {
        return tin[x] < tin[y];
    });
    cur = unique(tree + 1, tree + 1 + cur) - tree - 1;
 
    stack<int> st;
 
    rep(i, cur)
    {
        while(!st.empty() && tout[st.top()] < tout[tree[i]]) st.pop();
 
        if(sz(st)) adj[st.top()].pb(tree[i]);
        st.push(tree[i]);
    }
    ll res = INF;
    ford(i, cur, 1)
    {
        int u = tree[i];
        for(int v : adj[u])
            forn(j, 0, 1)
                minimize(dp[u][j], dp[v][j]);
        minimize(res, dp[u][0] + dp[u][1] - 2 * dist[u]);
    }
    ford(i, cur, 1) dp[tree[i]][0] = dp[tree[i]][1] = INF, adj[tree[i]].clear();
 
    return res;
}

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