oj.uz

Submission #843509

# Submission time Handle Problem Language Result Execution time Memory
843509 2023-09-04T03:56:56 Z daoquanglinh2007 Factories (JOI14_factories) C++17
15 / 100
 1603 ms 236880 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 = 1e6 + 5;
const ll oo = 1e18;

int n;
vector<vii> G;

vi vtn;
vector<vii> vt;

ll dis[mxN];
pii sparse[25][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] + w;
        dfs(u, v);
        sparse[0][++ecnt] = {dep[v], v};
    }

    tout[v] = ++timer;
}

void build_sparse() {
    assert(ecnt <= 2*n);
    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), res = min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
    return res;
}

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[]) {
    if (n > 5000) return 0;
    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), [&](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), [&](int u, int v) {
        return tin[u] < tin[v];
    });
    vtn.erase(unique(all(vtn)), vtn.end());

    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 < vtn.size(); i++){
        vt[vtn[i]].clear();
        cur[vtn[i]] = 0;
    }
    vtn.clear();

    return res;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < vtn.size(); i++){
      |                     ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43608 KB Output is correct
2 Correct 1360 ms 58708 KB Output is correct
3 Correct 1463 ms 58708 KB Output is correct
4 Correct 1448 ms 59080 KB Output is correct
5 Correct 1575 ms 59536 KB Output is correct
6 Correct 792 ms 58824 KB Output is correct
7 Correct 1481 ms 58716 KB Output is correct
8 Correct 1453 ms 58768 KB Output is correct
9 Correct 1603 ms 59336 KB Output is correct
10 Correct 776 ms 58704 KB Output is correct
11 Correct 1457 ms 58712 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43608 KB Output is correct
2 Incorrect 444 ms 236880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43608 KB Output is correct
2 Correct 1360 ms 58708 KB Output is correct
3 Correct 1463 ms 58708 KB Output is correct
4 Correct 1448 ms 59080 KB Output is correct
5 Correct 1575 ms 59536 KB Output is correct
6 Correct 792 ms 58824 KB Output is correct
7 Correct 1481 ms 58716 KB Output is correct
8 Correct 1453 ms 58768 KB Output is correct
9 Correct 1603 ms 59336 KB Output is correct
10 Correct 776 ms 58704 KB Output is correct
11 Correct 1457 ms 58712 KB Output is correct
12 Correct 11 ms 43608 KB Output is correct
13 Incorrect 444 ms 236880 KB Output isn't correct
14 Halted 0 ms 0 KB -