oj.uz

Submission #1065207

# Submission time Handle Problem Language Result Execution time Memory
1065207 2024-08-19T03:14:27 Z Boycl07 Factories (JOI14_factories) C++17
100 / 100
 1800 ms 171092 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, [&](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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24412 KB Output is correct
2 Correct 610 ms 42200 KB Output is correct
3 Correct 576 ms 42068 KB Output is correct
4 Correct 571 ms 42248 KB Output is correct
5 Correct 451 ms 42580 KB Output is correct
6 Correct 434 ms 42064 KB Output is correct
7 Correct 611 ms 42064 KB Output is correct
8 Correct 580 ms 42448 KB Output is correct
9 Correct 452 ms 42580 KB Output is correct
10 Correct 437 ms 42032 KB Output is correct
11 Correct 569 ms 42068 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Correct 866 ms 126804 KB Output is correct
3 Correct 1035 ms 129012 KB Output is correct
4 Correct 627 ms 127036 KB Output is correct
5 Correct 760 ms 163644 KB Output is correct
6 Correct 1115 ms 131152 KB Output is correct
7 Correct 857 ms 63516 KB Output is correct
8 Correct 510 ms 63688 KB Output is correct
9 Correct 413 ms 69716 KB Output is correct
10 Correct 826 ms 64816 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24412 KB Output is correct
2 Correct 610 ms 42200 KB Output is correct
3 Correct 576 ms 42068 KB Output is correct
4 Correct 571 ms 42248 KB Output is correct
5 Correct 451 ms 42580 KB Output is correct
6 Correct 434 ms 42064 KB Output is correct
7 Correct 611 ms 42064 KB Output is correct
8 Correct 580 ms 42448 KB Output is correct
9 Correct 452 ms 42580 KB Output is correct
10 Correct 437 ms 42032 KB Output is correct
11 Correct 569 ms 42068 KB Output is correct
12 Correct 11 ms 24152 KB Output is correct
13 Correct 866 ms 126804 KB Output is correct
14 Correct 1035 ms 129012 KB Output is correct
15 Correct 627 ms 127036 KB Output is correct
16 Correct 760 ms 163644 KB Output is correct
17 Correct 1115 ms 131152 KB Output is correct
18 Correct 857 ms 63516 KB Output is correct
19 Correct 510 ms 63688 KB Output is correct
20 Correct 413 ms 69716 KB Output is correct
21 Correct 826 ms 64816 KB Output is correct
22 Correct 1606 ms 139860 KB Output is correct
23 Correct 1441 ms 141652 KB Output is correct
24 Correct 1800 ms 144464 KB Output is correct
25 Correct 1752 ms 147720 KB Output is correct
26 Correct 1775 ms 139348 KB Output is correct
27 Correct 1307 ms 171092 KB Output is correct
28 Correct 1046 ms 139092 KB Output is correct
29 Correct 1787 ms 137972 KB Output is correct
30 Correct 1768 ms 137496 KB Output is correct
31 Correct 1718 ms 138064 KB Output is correct
32 Correct 716 ms 71504 KB Output is correct
33 Correct 572 ms 65732 KB Output is correct
34 Correct 832 ms 62012 KB Output is correct
35 Correct 823 ms 61776 KB Output is correct
36 Correct 885 ms 62800 KB Output is correct
37 Correct 918 ms 62604 KB Output is correct