oj.uz

Submission #843488

# Submission time Handle Problem Language Result Execution time Memory
843488 2023-09-04T03:34:39 Z daoquanglinh2007 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 152788 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);
    int res = min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
    //assert(res > 0);
    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[]) {
    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 23 ms 45688 KB Output is correct
2 Correct 1374 ms 56668 KB Output is correct
3 Correct 1527 ms 56668 KB Output is correct
4 Correct 1454 ms 56996 KB Output is correct
5 Correct 1589 ms 57284 KB Output is correct
6 Correct 813 ms 56660 KB Output is correct
7 Correct 1523 ms 56672 KB Output is correct
8 Correct 1475 ms 56724 KB Output is correct
9 Correct 1606 ms 57280 KB Output is correct
10 Correct 824 ms 56924 KB Output is correct
11 Correct 1525 ms 56776 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 45660 KB Output is correct
2 Execution timed out 8009 ms 152788 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 45688 KB Output is correct
2 Correct 1374 ms 56668 KB Output is correct
3 Correct 1527 ms 56668 KB Output is correct
4 Correct 1454 ms 56996 KB Output is correct
5 Correct 1589 ms 57284 KB Output is correct
6 Correct 813 ms 56660 KB Output is correct
7 Correct 1523 ms 56672 KB Output is correct
8 Correct 1475 ms 56724 KB Output is correct
9 Correct 1606 ms 57280 KB Output is correct
10 Correct 824 ms 56924 KB Output is correct
11 Correct 1525 ms 56776 KB Output is correct
12 Correct 12 ms 45660 KB Output is correct
13 Execution timed out 8009 ms 152788 KB Time limit exceeded
14 Halted 0 ms 0 KB -