oj.uz

Submission #1065195

# Submission time Handle Problem Language Result Execution time Memory
1065195 2024-08-19T03:02:16 Z Boycl07 Factories (JOI14_factories) C++17
0 / 100
 21 ms 24920 KB 
#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);
    for(int i = cur - 1; i >= 1; --i) tree[++cur] = lca(tree[i], tree[i + 1]);
    sort(tree + 1, tree + 1 + cur);
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 24920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 24668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 24920 KB Output isn't correct
2 Halted 0 ms 0 KB -