oj.uz

Submission #843446

# Submission time Handle Problem Language Result Execution time Memory
843446 2023-09-04T02:37:27 Z hotboy2703 Factories (JOI14_factories) C++14
15 / 100
 4122 ms 55300 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;
//vii -> vll
vector<vector <pair <int,ll> > > vt;

ll dis[mxN];
//mxN
pii sparse[19][mxN * 2];
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;
    //dis
    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, 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;
        //vt, G
        for(auto &[u, w] : vt[v]) {
            if(u == p) continue;
            //cout<<u<<' '<<v<<' '<<w<<' '<<dis[u]<<' '<<dis[v]<<'\n';
            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 (auto x:vtn){
        cur[x] = 0;
        vt[x].clear();
    }
    /*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;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 41564 KB Output is correct
2 Correct 4006 ms 54716 KB Output is correct
3 Correct 3712 ms 54736 KB Output is correct
4 Correct 3895 ms 54772 KB Output is correct
5 Correct 4117 ms 55296 KB Output is correct
6 Correct 3519 ms 55020 KB Output is correct
7 Correct 3697 ms 54732 KB Output is correct
8 Correct 3844 ms 54772 KB Output is correct
9 Correct 4122 ms 55300 KB Output is correct
10 Correct 3569 ms 54776 KB Output is correct
11 Correct 3733 ms 54728 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 41560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 41564 KB Output is correct
2 Correct 4006 ms 54716 KB Output is correct
3 Correct 3712 ms 54736 KB Output is correct
4 Correct 3895 ms 54772 KB Output is correct
5 Correct 4117 ms 55296 KB Output is correct
6 Correct 3519 ms 55020 KB Output is correct
7 Correct 3697 ms 54732 KB Output is correct
8 Correct 3844 ms 54772 KB Output is correct
9 Correct 4122 ms 55300 KB Output is correct
10 Correct 3569 ms 54776 KB Output is correct
11 Correct 3733 ms 54728 KB Output is correct
12 Incorrect 25 ms 41560 KB Output isn't correct
13 Halted 0 ms 0 KB -