oj.uz

Submission #843415

# Submission time Handle Problem Language Result Execution time Memory
843415 2023-09-04T01:48:44 Z socpite Factories (JOI14_factories) C++14
15 / 100
 8000 ms 152476 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] + 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;
        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], -1);
 
    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:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for(auto &[u, w] : G[v]) {
      |               ^
factories.cpp: In lambda function:
factories.cpp:121:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         for(auto &[u, w] : G[v]) {
      |                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45660 KB Output is correct
2 Correct 1403 ms 57544 KB Output is correct
3 Correct 1544 ms 57492 KB Output is correct
4 Correct 1595 ms 57728 KB Output is correct
5 Correct 1651 ms 57284 KB Output is correct
6 Correct 1004 ms 56992 KB Output is correct
7 Correct 1653 ms 57616 KB Output is correct
8 Correct 1614 ms 57412 KB Output is correct
9 Correct 1681 ms 57240 KB Output is correct
10 Correct 804 ms 56996 KB Output is correct
11 Correct 1597 ms 57404 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45656 KB Output is correct
2 Execution timed out 8052 ms 152476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45660 KB Output is correct
2 Correct 1403 ms 57544 KB Output is correct
3 Correct 1544 ms 57492 KB Output is correct
4 Correct 1595 ms 57728 KB Output is correct
5 Correct 1651 ms 57284 KB Output is correct
6 Correct 1004 ms 56992 KB Output is correct
7 Correct 1653 ms 57616 KB Output is correct
8 Correct 1614 ms 57412 KB Output is correct
9 Correct 1681 ms 57240 KB Output is correct
10 Correct 804 ms 56996 KB Output is correct
11 Correct 1597 ms 57404 KB Output is correct
12 Correct 15 ms 45656 KB Output is correct
13 Execution timed out 8052 ms 152476 KB Time limit exceeded
14 Halted 0 ms 0 KB -