oj.uz

Submission #843374

# Submission time Handle Problem Language Result Execution time Memory
843374 2023-09-04T01:10:43 Z anhduc2701 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 171476 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<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;
 
const int mxN = 5e5 + 5;
const ll oo = 1e18;
 
int n;
vector<vii> G;
 
vi vtn;
vector<vii> vt;
 
ll dis[mxN];
pii sparse[19][mxN];
int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];
 
void dfs(int v, int 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] + p;
        dfs(u, v);
        sparse[0][++ecnt] = {dep[v], v};
    }
 
    tout[v] = ++timer;
}
 
void build_sparse() {
    for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
        for(int j = 1; j <= ecnt - (p << 1) + 1; ++j)
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}
 
bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int LCA(int u, int v) {
    int l = ap[u], r = ap[v];
    if(l > r) swap(l, r);
    int 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(int 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(int i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        q.emplace(X[i], 0);
        vtn.emplace_back(X[i]);
    }
    for(int i = 0; i < T; ++i) {
        cur[Y[i]] = 2;
        vtn.emplace_back(Y[i]);
    }
    sort(all(vtn));
    vtn.erase(unique(all(vtn)), vtn.end());
    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });
    for(int i = 0; i < S + T - 1; ++i) {
        vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
    }
    sort(all(vtn));
    vtn.erase(unique(all(vtn)), vtn.end());
    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });
    auto add_vt = [&](int u, int v, int w) {
        vt[u].emplace_back(v, w);
        vt[v].emplace_back(u, w);
    };
    stack<int> s;
    for(int 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, int v, int 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(int 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(int i = 0; i < S; ++i) {
        cur[X[i]] = 0;
        vt[X[i]].clear();
    }
    for(int 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 26 ms 45916 KB Output is correct
2 Correct 1517 ms 67060 KB Output is correct
3 Correct 1704 ms 67072 KB Output is correct
4 Correct 1714 ms 67384 KB Output is correct
5 Correct 1763 ms 67160 KB Output is correct
6 Correct 1014 ms 66620 KB Output is correct
7 Correct 1689 ms 67056 KB Output is correct
8 Correct 1673 ms 67328 KB Output is correct
9 Correct 1724 ms 66712 KB Output is correct
10 Correct 1022 ms 66388 KB Output is correct
11 Correct 1713 ms 66964 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 45916 KB Output is correct
2 Correct 1517 ms 67060 KB Output is correct
3 Correct 1704 ms 67072 KB Output is correct
4 Correct 1714 ms 67384 KB Output is correct
5 Correct 1763 ms 67160 KB Output is correct
6 Correct 1014 ms 66620 KB Output is correct
7 Correct 1689 ms 67056 KB Output is correct
8 Correct 1673 ms 67328 KB Output is correct
9 Correct 1724 ms 66712 KB Output is correct
10 Correct 1022 ms 66388 KB Output is correct
11 Correct 1713 ms 66964 KB Output is correct
12 Correct 12 ms 45660 KB Output is correct
13 Execution timed out 8007 ms 171476 KB Time limit exceeded
14 Halted 0 ms 0 KB -