oj.uz

Submission #246892

# Submission time Handle Problem Language Result Execution time Memory
246892 2020-07-10T13:34:06 Z receed Factories (JOI14_factories) C++14
33 / 100
 8000 ms 135372 KB 
#include "factories.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 500001, L = 19;
vector<pair<ll, ll>> g[N];
int tin[N], tout[N], ct, up[L][N], th[N], par[N], st[N];
ll h[N], d1[N], d2[N], inf = 1e16;

void dfs(int v, int p) {
    up[0][v] = p;
    tin[v] = ++ct;
    for (auto &u : g[v])
        if (u.first != p) {
            h[u.first] = h[v] + u.second;
            th[u.first] = th[v] + 1;
            dfs(u.first, v);
        }
    tout[v] = ++ct;
}

int lca(int u, int v) {
    if (th[u] > th[v])
        swap(u, v);
    for (int i = L - 1; i >= 0; i--)
        if (th[up[i][v]] >= th[u])
            v = up[i][v];
    if (u == v)
        return u;
    for (int i = L - 1; i >= 0; i--)
        if (up[i][u] != up[i][v]) {
            u = up[i][u];
            v = up[i][v];
        }
    return up[0][u];
}

void Init(int n, int a[], int b[], int d[]) {
    rep(i, n - 1) {
        g[a[i]].push_back({b[i], d[i]});
        g[b[i]].push_back({a[i], d[i]});
    }
    dfs(0, 0);
    rep(i, L - 1)
        rep(j, n)
            up[i + 1][j] = up[i][up[i][j]];
    rep(i, n)
        d1[i] = d2[i] = inf;
}

long long Query(int s, int x[], int t, int y[]) {
    vector<int> li;
    rep(i, s) {
        li.push_back(x[i]);
        d1[x[i]] = 0;
    }
    rep(i, t) {
        li.push_back(y[i]);
        d2[y[i]] = 0;
    }
    sort(all(li), [](int v1, int v2) {return tin[v1] < tin[v2];});
    int k = li.size();
    rep(i, k - 1)
        li.push_back(lca(li[i], li[i + 1]));
    sort(all(li), [](int v1, int v2) {return tin[v1] < tin[v2];});
    li.resize(unique(all(li)) - li.begin());
    int sp = 0;
    for (int i : li) {
        if (sp == 0)
            st[sp++] = i;
        else {
            while (tout[st[sp - 1]] < tout[i])
                sp--;
            par[i] = st[sp - 1];
            st[sp++] = i;
        }
    }
    ll ans = inf;
    for (int i = li.size() - 1; i > 0; i--) {
        ll v = li[i], cd = h[v] - h[par[v]];
        ans = min(ans, min(d1[v] + d2[par[v]], d2[v] + d1[par[v]]) + cd);
        d1[par[v]] = min(d1[par[v]], d1[v] + cd);
        d2[par[v]] = min(d2[par[v]], d2[v] + cd);
    }
    for (int i : li)
        d1[i] = d2[i] = inf;
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12672 KB Output is correct
2 Correct 1199 ms 25464 KB Output is correct
3 Correct 1207 ms 25544 KB Output is correct
4 Correct 1183 ms 25628 KB Output is correct
5 Correct 1049 ms 25208 KB Output is correct
6 Correct 1083 ms 24952 KB Output is correct
7 Correct 1259 ms 25080 KB Output is correct
8 Correct 1183 ms 24956 KB Output is correct
9 Correct 1041 ms 25080 KB Output is correct
10 Correct 1066 ms 24824 KB Output is correct
11 Correct 1193 ms 24824 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12416 KB Output is correct
2 Correct 3495 ms 115836 KB Output is correct
3 Correct 4445 ms 117116 KB Output is correct
4 Correct 3305 ms 111200 KB Output is correct
5 Correct 3584 ms 133656 KB Output is correct
6 Correct 4647 ms 115676 KB Output is correct
7 Correct 4523 ms 42080 KB Output is correct
8 Correct 4251 ms 42228 KB Output is correct
9 Correct 3617 ms 46324 KB Output is correct
10 Correct 4713 ms 44676 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12672 KB Output is correct
2 Correct 1199 ms 25464 KB Output is correct
3 Correct 1207 ms 25544 KB Output is correct
4 Correct 1183 ms 25628 KB Output is correct
5 Correct 1049 ms 25208 KB Output is correct
6 Correct 1083 ms 24952 KB Output is correct
7 Correct 1259 ms 25080 KB Output is correct
8 Correct 1183 ms 24956 KB Output is correct
9 Correct 1041 ms 25080 KB Output is correct
10 Correct 1066 ms 24824 KB Output is correct
11 Correct 1193 ms 24824 KB Output is correct
12 Correct 15 ms 12416 KB Output is correct
13 Correct 3495 ms 115836 KB Output is correct
14 Correct 4445 ms 117116 KB Output is correct
15 Correct 3305 ms 111200 KB Output is correct
16 Correct 3584 ms 133656 KB Output is correct
17 Correct 4647 ms 115676 KB Output is correct
18 Correct 4523 ms 42080 KB Output is correct
19 Correct 4251 ms 42228 KB Output is correct
20 Correct 3617 ms 46324 KB Output is correct
21 Correct 4713 ms 44676 KB Output is correct
22 Correct 6019 ms 114028 KB Output is correct
23 Correct 5903 ms 115816 KB Output is correct
24 Correct 6113 ms 117028 KB Output is correct
25 Correct 6374 ms 119476 KB Output is correct
26 Correct 7430 ms 115192 KB Output is correct
27 Correct 5832 ms 135372 KB Output is correct
28 Correct 5714 ms 116816 KB Output is correct
29 Execution timed out 8042 ms 117380 KB Time limit exceeded
30 Halted 0 ms 0 KB -