oj.uz

Submission #246726

# Submission time Handle Problem Language Result Execution time Memory
246726 2020-07-10T02:32:17 Z LifeHappen__ Factories (JOI14_factories) C++14
100 / 100
 4305 ms 151784 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

#define forinc(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define fordec(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define rep(i, a) forinc(i, 1, a)
#define repv(i, a) forinc(i, 0, a - 1)
#define forv(a, b) for(auto &a : b)

#define ii pair<int, long long>
#define fi first
#define se second
#define reset(f, x) memset(f, x, sizeof(f))
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair

#define bit(x, i) (x >> (i - 1) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))

const int N = 5e5 + 5;
const int _N = 5005;
const long long INF = 1e16;
int n, que;
vector<ii> ad[N];
int st[N], en[N], id, pd[N][25], dd[N];
long long d[N], ans, pf[N], sf[N];

void Init(int n, int A[], int B[], int D[]) {
    repv(i, n - 1) {
        int u = A[i], v = B[i], c = D[i];
        u++; v++;
        ad[u].eb(v, c);
        ad[v].eb(u, c);
    }
    function<void(int, int)> dfs = [&](int u, int par) {
        st[u] = ++id;
        forinc(i, 1, 20) pd[u][i] = pd[pd[u][i - 1]][i - 1];
        forv(v, ad[u]) if(v.fi != par) {
            pd[v.fi][0] = u;
            d[v.fi] = d[u] + 1ll * v.se;
            dfs(v.fi, u);
        }
        en[u] = ++id;
    };
    dfs(1, 0);
    forinc(i, 1, n) ad[i].clear();
}
int anc(int u, int v) {
    return (st[u] <= st[v] && en[u] >= en[v]) || !u;
}
int lca(int u, int v){
    if(anc(u, v)) return u;
    if(anc(v, u)) return v;
    fordec(i, 20, 0) if(!anc(pd[u][i], v)) u = pd[u][i];
    return pd[u][0];
}
bool cmp(int x, int y) {return make_pair(st[x], en[x]) < make_pair(st[y], en[y]);}
long long dist(int u, int v) {return 1ll * d[u] + 1ll * d[v] - 2ll * d[lca(u, v)];}
long long Query(int s, int S[], int t, int T[]) {
    vector<int> no;
    repv(i, s) no.pb(S[i] + 1), dd[S[i] + 1] = 1;
    repv(i, t) no.pb(T[i] + 1), dd[T[i] + 1] |= 2;
    sort(all(no), cmp);
    repv(i, no.size() - 1) no.pb(lca(no[i], no[i + 1]));
    sort(all(no)); no.erase(unique(all(no)), end(no));
    sort(all(no), cmp);
    stack<int> kek;
    forv(v, no) {
        while(kek.size() && en[v] >= en[kek.top()]) kek.pop();
        if(kek.size()) {
            ad[kek.top()].eb(v, d[v] - d[kek.top()]);
        }
        kek.push(v);
    }
    ans = INF;
    function<void(int)> dfs = [&](int u) {
        long long &x = pf[u], &y = sf[u];
        x = (dd[u] & 1) ? 0 : INF;
        y = (dd[u] & 2) ? 0 : INF;
        forv(v, ad[u]) {
            dfs(v.fi);
            x = min(x, pf[v.fi] + 1ll * v.se);
            y = min(y, sf[v.fi] + 1ll * v.se);
        }
        ans = min(ans, x + y);
    };
    ans = INF;
    dfs(no[0]);
    forv(v, no) pf[v] = sf[v] = dd[v] = 0, ad[v].clear();
    return ans;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //if(fopen("inp.txt", "r")){
        freopen("inp.txt", "r", stdin);
    //}
    cin >> n >> que;
    static int A[_N], B[_N], D[_N];
    repv(i, n - 1) cin >> A[i] >> B[i] >> D[i];
    Init(n, A, B, D);
    while(que--) {
        int s, t;
        cin >> s >> t;
        static int S[_N], T[_N];
        repv(i, s) cin >> S[i];
        repv(i, t) cin >> T[i];
        cout << Query(s, S, t, T) << '\n';
    }
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12544 KB Output is correct
2 Correct 1314 ms 21368 KB Output is correct
3 Correct 1311 ms 21312 KB Output is correct
4 Correct 1289 ms 21368 KB Output is correct
5 Correct 1096 ms 28536 KB Output is correct
6 Correct 1089 ms 28136 KB Output is correct
7 Correct 1310 ms 28156 KB Output is correct
8 Correct 1288 ms 28224 KB Output is correct
9 Correct 1038 ms 28408 KB Output is correct
10 Correct 1131 ms 28192 KB Output is correct
11 Correct 1337 ms 28152 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12416 KB Output is correct
2 Correct 1815 ms 117488 KB Output is correct
3 Correct 2388 ms 121380 KB Output is correct
4 Correct 1374 ms 115092 KB Output is correct
5 Correct 1767 ms 151784 KB Output is correct
6 Correct 2649 ms 122604 KB Output is correct
7 Correct 2278 ms 48376 KB Output is correct
8 Correct 1409 ms 47588 KB Output is correct
9 Correct 1312 ms 52408 KB Output is correct
10 Correct 2341 ms 49236 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12544 KB Output is correct
2 Correct 1314 ms 21368 KB Output is correct
3 Correct 1311 ms 21312 KB Output is correct
4 Correct 1289 ms 21368 KB Output is correct
5 Correct 1096 ms 28536 KB Output is correct
6 Correct 1089 ms 28136 KB Output is correct
7 Correct 1310 ms 28156 KB Output is correct
8 Correct 1288 ms 28224 KB Output is correct
9 Correct 1038 ms 28408 KB Output is correct
10 Correct 1131 ms 28192 KB Output is correct
11 Correct 1337 ms 28152 KB Output is correct
12 Correct 14 ms 12416 KB Output is correct
13 Correct 1815 ms 117488 KB Output is correct
14 Correct 2388 ms 121380 KB Output is correct
15 Correct 1374 ms 115092 KB Output is correct
16 Correct 1767 ms 151784 KB Output is correct
17 Correct 2649 ms 122604 KB Output is correct
18 Correct 2278 ms 48376 KB Output is correct
19 Correct 1409 ms 47588 KB Output is correct
20 Correct 1312 ms 52408 KB Output is correct
21 Correct 2341 ms 49236 KB Output is correct
22 Correct 3550 ms 120740 KB Output is correct
23 Correct 3531 ms 122332 KB Output is correct
24 Correct 4176 ms 124832 KB Output is correct
25 Correct 4105 ms 127504 KB Output is correct
26 Correct 4288 ms 123188 KB Output is correct
27 Correct 3225 ms 149692 KB Output is correct
28 Correct 2464 ms 121184 KB Output is correct
29 Correct 4196 ms 123000 KB Output is correct
30 Correct 4305 ms 122036 KB Output is correct
31 Correct 4119 ms 122876 KB Output is correct
32 Correct 1904 ms 52688 KB Output is correct
33 Correct 1776 ms 47376 KB Output is correct
34 Correct 2246 ms 43768 KB Output is correct
35 Correct 2201 ms 43896 KB Output is correct
36 Correct 2450 ms 44860 KB Output is correct
37 Correct 2524 ms 45048 KB Output is correct