oj.uz

Submission #843460

# Submission time Handle Problem Language Result Execution time Memory
843460 2023-09-04T02:53:38 Z adaawf Factories (JOI14_factories) C++14
100 / 100
 4786 ms 299812 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), [&](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 < 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;
}*/
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
long long int f[500005];
int n, d[500005], tin[500005], b[2000005], l[2000005], z = 0;
vector<int> gg[500005], g[500005];
int p[500005][20], pp[2000005][22];
void bfs(int x) {
    queue<int> q;
    q.push(x);
    p[x][0] = x;
    f[x] = d[x] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int j = 1; j <= 19; j++) {
             p[u][j] = p[p[u][j - 1]][j - 1];
             if (p[u][j] == 0) break;
        }
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (d[u] + 1 < d[v]) {
                d[v] = d[u] + 1;
                f[v] = f[u] + gg[u][i];
                p[v][0] = u;
                q.push(v);
            }
        }
    }
}
void dfs(int x, int p) {
    b[++z] = x;
    pp[z][0] = x;
    tin[x] = z;
    for (int w : g[x]) {
        if (w == p) continue;
        dfs(w, x);
        b[++z] = x;
        pp[z][0] = x;
    }
    b[++z] = x;
    pp[z][0] = x;
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < 500000; i++) {
        f[i] = 999999999999999999;
        d[i] = n * 2;
    }
    for (int i = 0; i < n - 1; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back(v);
        g[v].push_back(u);
        gg[u].push_back(w);
        gg[v].push_back(w);
    }
    bfs(0);
    dfs(0, -1);
    for (int i = 2; i <= 2000000; i++) l[i] = l[i / 2] + 1;
    for (int i = 1; (1 << i) <= z; i++) {
        for (int j = 1; j <= z - (1 << i) + 1; j++) {
            if (d[pp[j][i - 1]] < d[pp[j + (1 << (i - 1))][i - 1]]) pp[j][i] = pp[j][i - 1];
            else pp[j][i] = pp[j + (1 << (i - 1))][i - 1];
        }
    }
}
int lca(int u, int v) {
    int x = tin[u], y = tin[v];
    if (y <= x) swap(x, y);
    int g = l[y - x + 1];
    int h = pp[x][g], k = pp[y - (1 << g) + 1][g];
    if (d[h] < d[k]) return h;
    return k;
}
long long int check(int u, int v) {
    return f[u] + f[v] - f[lca(u, v)] * 2;
}
long long int Query(int S, int X[], int T, int Y[]) {
    if (S > 100 && T > 100) {
        vector<long long int> ff(n, 999999999999999999);
        vector<bool> dda(n, 0), dd(n, 0);
        for (int i = 0; i < T; i++) {
            dda[Y[i]] = 1;
        }
        priority_queue<pair<long long int, long long int>> q;
        for (int i = 0; i < S; i++) {
            q.push({0, X[i]});
            ff[X[i]] = 0;
        }
        while (!q.empty()) {
            int u = q.top().second;
            q.pop();
            if (dd[u] == 1) continue;
            dd[u] = 1;
            if (dda[u] == 1) return ff[u];
            for (int i = 0; i < g[u].size(); i++) {
                int v = g[u][i], w = gg[u][i];
                if (ff[u] + w < ff[v]) {
                    ff[v] = ff[u] + w;
                    q.push({-ff[v], v});
                }
            }
        }
    }
    long long int res = 999999999999999999;
    for (int i = 0; i < S; i++) {
        for (int j = 0; j < T; j++) {
            res = min(res, check(X[i], Y[j]));
        }
    }
    return res;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 68184 KB Output is correct
2 Correct 332 ms 72844 KB Output is correct
3 Correct 282 ms 72692 KB Output is correct
4 Correct 376 ms 72972 KB Output is correct
5 Correct 321 ms 73104 KB Output is correct
6 Correct 421 ms 73020 KB Output is correct
7 Correct 289 ms 72952 KB Output is correct
8 Correct 279 ms 72688 KB Output is correct
9 Correct 323 ms 73104 KB Output is correct
10 Correct 454 ms 73024 KB Output is correct
11 Correct 290 ms 72800 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 68184 KB Output is correct
2 Correct 1102 ms 273908 KB Output is correct
3 Correct 1262 ms 275692 KB Output is correct
4 Correct 811 ms 276144 KB Output is correct
5 Correct 1315 ms 299592 KB Output is correct
6 Correct 1191 ms 275784 KB Output is correct
7 Correct 803 ms 110676 KB Output is correct
8 Correct 572 ms 111560 KB Output is correct
9 Correct 576 ms 113912 KB Output is correct
10 Correct 604 ms 111092 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 68184 KB Output is correct
2 Correct 332 ms 72844 KB Output is correct
3 Correct 282 ms 72692 KB Output is correct
4 Correct 376 ms 72972 KB Output is correct
5 Correct 321 ms 73104 KB Output is correct
6 Correct 421 ms 73020 KB Output is correct
7 Correct 289 ms 72952 KB Output is correct
8 Correct 279 ms 72688 KB Output is correct
9 Correct 323 ms 73104 KB Output is correct
10 Correct 454 ms 73024 KB Output is correct
11 Correct 290 ms 72800 KB Output is correct
12 Correct 12 ms 68184 KB Output is correct
13 Correct 1102 ms 273908 KB Output is correct
14 Correct 1262 ms 275692 KB Output is correct
15 Correct 811 ms 276144 KB Output is correct
16 Correct 1315 ms 299592 KB Output is correct
17 Correct 1191 ms 275784 KB Output is correct
18 Correct 803 ms 110676 KB Output is correct
19 Correct 572 ms 111560 KB Output is correct
20 Correct 576 ms 113912 KB Output is correct
21 Correct 604 ms 111092 KB Output is correct
22 Correct 1395 ms 279924 KB Output is correct
23 Correct 1553 ms 283556 KB Output is correct
24 Correct 1478 ms 281496 KB Output is correct
25 Correct 1510 ms 282220 KB Output is correct
26 Correct 1751 ms 278864 KB Output is correct
27 Correct 1572 ms 299812 KB Output is correct
28 Correct 1528 ms 295272 KB Output is correct
29 Correct 3471 ms 278356 KB Output is correct
30 Correct 4089 ms 277920 KB Output is correct
31 Correct 4786 ms 278872 KB Output is correct
32 Correct 522 ms 115840 KB Output is correct
33 Correct 518 ms 114672 KB Output is correct
34 Correct 475 ms 110580 KB Output is correct
35 Correct 497 ms 110584 KB Output is correct
36 Correct 548 ms 110932 KB Output is correct
37 Correct 561 ms 110948 KB Output is correct