oj.uz

Submission #843497

# Submission time Handle Problem Language Result Execution time Memory
843497 2023-09-04T03:42:18 Z bachhoangxuan Factories (JOI14_factories) C++17
15 / 100
 8000 ms 399820 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<ll, ll>
#define vi vector<ll>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (ll)x.size()
using namespace std;

const ll mxN = 5e5 + 5;
const ll oo = 1e18;

ll n;
vector<vii> G;

vi vtn;
vector<vii> vt;

ll dis[mxN];
pii sparse[21][2*mxN];
ll timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];

void dfs(ll v, ll p) {
    tin[v] = ++timer;
    dep[v] = dep[p] + 1;
    sparse[0][++ecnt] = {dep[v], v};
    ap[v] = ecnt;

    for(auto &[u, w] : G[v]) {
        if(u == p) continue;
        dis[u] = dis[v] + w;
        dfs(u, v);
        sparse[0][++ecnt] = {dep[v], v};
    }

    tout[v] = ++timer;
}

void build_sparse() {
    for(ll p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
        for(ll j = 1; j <= ecnt - (p << 1) + 1; ++j)
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}

bool is_ancestor(ll u, ll v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

ll LCA(ll u, ll v) {
    ll l = ap[u], r = ap[v];
    if(l > r) swap(l, r);
    ll len = r - l + 1, lg_len = __lg(len);
    return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    G.resize(n); vt.resize(n);
    for(ll i = 0; i < N - 1; ++i) {
        G[A[i]].emplace_back(B[i], D[i]);
        G[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0); build_sparse();
}

long long Query(int S, int X[], int T,int Y[]) {
    queue<pii> q;

    for(ll i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        q.emplace(X[i], 0);
        vtn.emplace_back(X[i]);
    }
    for(ll i = 0; i < T; ++i) {
        cur[Y[i]] = 2;
        vtn.emplace_back(Y[i]);
    }

    sort(all(vtn), [&](ll u, ll v) {
        return tin[u] < tin[v];
    });

    for(ll i = 0; i < S + T - 1; ++i) {
        vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
    }

    sort(all(vtn), [&](ll u, ll v) {
        return tin[u] < tin[v];
    });
    vtn.erase(unique(all(vtn)), vtn.end());

    auto add_vt = [&](ll u, ll v, ll w) {
        vt[u].emplace_back(v, w);
        vt[v].emplace_back(u, w);
    };

    stack<ll> s;
    for(ll i = 0; i < isz(vtn); ++i) {
        while(not s.empty() && not is_ancestor(s.top(), vtn[i])) s.pop();
        if(s.empty()) s.emplace(vtn[i]);
        else {
            add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]);
            s.emplace(vtn[i]);
        }
    }

    ll res = oo;

    auto dfs = [&](auto self, ll v, ll p) -> vll {
        vll cur_dis(2, oo);
        if(cur[v]) cur_dis[cur[v] - 1] = 0;
        for(auto &[u, w] : G[v]) {
            if(u == p) continue;
            vll tmp = self(self, u, v);
            for(ll i = 0; i < 2; ++i)
                cur_dis[i] = min(cur_dis[i], tmp[i] + w);
        }
        res = min(res, accumulate(all(cur_dis), 0LL));
        return cur_dis;
    };

    dfs(dfs, vtn[0], 0);

    for(ll i = 0; i < S; ++i) {
        cur[X[i]] = 0;
        vt[X[i]].clear();
    }
    for(ll i = 0; i < T; ++i) {
        cur[Y[i]] = 0;
        vt[Y[i]].clear();
    }
    vtn.clear();

    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43612 KB Output is correct
2 Correct 1346 ms 60348 KB Output is correct
3 Correct 1532 ms 60468 KB Output is correct
4 Correct 1570 ms 61060 KB Output is correct
5 Correct 1627 ms 59732 KB Output is correct
6 Correct 831 ms 59252 KB Output is correct
7 Correct 1540 ms 60520 KB Output is correct
8 Correct 1546 ms 61000 KB Output is correct
9 Correct 1618 ms 59732 KB Output is correct
10 Correct 806 ms 59344 KB Output is correct
11 Correct 1585 ms 61032 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 43612 KB Output is correct
2 Execution timed out 8029 ms 399820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43612 KB Output is correct
2 Correct 1346 ms 60348 KB Output is correct
3 Correct 1532 ms 60468 KB Output is correct
4 Correct 1570 ms 61060 KB Output is correct
5 Correct 1627 ms 59732 KB Output is correct
6 Correct 831 ms 59252 KB Output is correct
7 Correct 1540 ms 60520 KB Output is correct
8 Correct 1546 ms 61000 KB Output is correct
9 Correct 1618 ms 59732 KB Output is correct
10 Correct 806 ms 59344 KB Output is correct
11 Correct 1585 ms 61032 KB Output is correct
12 Correct 12 ms 43612 KB Output is correct
13 Execution timed out 8029 ms 399820 KB Time limit exceeded
14 Halted 0 ms 0 KB -