oj.uz

Submission #843430

# Submission time Handle Problem Language Result Execution time Memory
843430 2023-09-04T02:03:45 Z socpite Factories (JOI14_factories) C++14
100 / 100
 2077 ms 305172 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<vector<pair<int, long long>>> vt;

ll dis[mxN];
pii sparse[20][2 * 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()
{
    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, long long 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] : vt[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], -1);

    for (auto v : vtn)
    {
        cur[v] = 0;
        vt[v].clear();
    }
    vtn.clear();

    return res;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:39:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for (auto &[u, w] : G[v])
      |                ^
factories.cpp: In lambda function:
factories.cpp:141:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |         for (auto &[u, w] : vt[v])
      |                    ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 557 ms 58704 KB Output is correct
3 Correct 566 ms 58960 KB Output is correct
4 Correct 555 ms 58960 KB Output is correct
5 Correct 522 ms 59216 KB Output is correct
6 Correct 344 ms 58704 KB Output is correct
7 Correct 543 ms 58792 KB Output is correct
8 Correct 553 ms 58704 KB Output is correct
9 Correct 523 ms 59216 KB Output is correct
10 Correct 345 ms 58824 KB Output is correct
11 Correct 572 ms 58824 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 45656 KB Output is correct
2 Correct 895 ms 246064 KB Output is correct
3 Correct 903 ms 268980 KB Output is correct
4 Correct 712 ms 265176 KB Output is correct
5 Correct 908 ms 302036 KB Output is correct
6 Correct 1002 ms 270336 KB Output is correct
7 Correct 673 ms 121396 KB Output is correct
8 Correct 556 ms 120516 KB Output is correct
9 Correct 528 ms 125740 KB Output is correct
10 Correct 649 ms 122160 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 557 ms 58704 KB Output is correct
3 Correct 566 ms 58960 KB Output is correct
4 Correct 555 ms 58960 KB Output is correct
5 Correct 522 ms 59216 KB Output is correct
6 Correct 344 ms 58704 KB Output is correct
7 Correct 543 ms 58792 KB Output is correct
8 Correct 553 ms 58704 KB Output is correct
9 Correct 523 ms 59216 KB Output is correct
10 Correct 345 ms 58824 KB Output is correct
11 Correct 572 ms 58824 KB Output is correct
12 Correct 6 ms 45656 KB Output is correct
13 Correct 895 ms 246064 KB Output is correct
14 Correct 903 ms 268980 KB Output is correct
15 Correct 712 ms 265176 KB Output is correct
16 Correct 908 ms 302036 KB Output is correct
17 Correct 1002 ms 270336 KB Output is correct
18 Correct 673 ms 121396 KB Output is correct
19 Correct 556 ms 120516 KB Output is correct
20 Correct 528 ms 125740 KB Output is correct
21 Correct 649 ms 122160 KB Output is correct
22 Correct 2021 ms 278676 KB Output is correct
23 Correct 1639 ms 278692 KB Output is correct
24 Correct 2077 ms 282816 KB Output is correct
25 Correct 1916 ms 284928 KB Output is correct
26 Correct 1746 ms 277824 KB Output is correct
27 Correct 1844 ms 305172 KB Output is correct
28 Correct 1344 ms 275784 KB Output is correct
29 Correct 1701 ms 276428 KB Output is correct
30 Correct 1621 ms 276108 KB Output is correct
31 Correct 1539 ms 276484 KB Output is correct
32 Correct 861 ms 130212 KB Output is correct
33 Correct 572 ms 123484 KB Output is correct
34 Correct 873 ms 121064 KB Output is correct
35 Correct 839 ms 120624 KB Output is correct
36 Correct 945 ms 121828 KB Output is correct
37 Correct 909 ms 121236 KB Output is correct