oj.uz

답안 #246902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246902 2020-07-10T13:45:59 Z receed 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 129544 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 = 18;
vector<pair<ll, ll>> g[N];
int tin[N], tout[N], ct, up[L][N], th[N], par[N], st[N], li[N * 2];
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[]) {
    int lp = 0;
    rep(i, s) {
        li[lp++] = x[i];
        d1[x[i]] = 0;
    }
    rep(i, t) {
        li[lp++] = y[i];
        d2[y[i]] = 0;
    }
    sort(li, li + lp, [](int v1, int v2) {return tin[v1] < tin[v2];});
    int k = lp;
    rep(i, k - 1)
        li[lp++] = lca(li[i], li[i + 1]);
    sort(li, li + lp, [](int v1, int v2) {return tin[v1] < tin[v2];});
    lp = unique(li, li + lp) - li;
    int sp = 0;
    rep(j, lp) {
        int i = li[j];
        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 = lp - 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);
    }
    rep(i, lp)
        d1[li[i]] = d2[li[i]] = inf;
    return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 12800 KB Output is correct
2 Correct 1147 ms 23648 KB Output is correct
3 Correct 1167 ms 23532 KB Output is correct
4 Correct 1151 ms 23576 KB Output is correct
5 Correct 1216 ms 23644 KB Output is correct
6 Correct 991 ms 23596 KB Output is correct
7 Correct 1130 ms 23460 KB Output is correct
8 Correct 1123 ms 23688 KB Output is correct
9 Correct 1040 ms 23576 KB Output is correct
10 Correct 1014 ms 23516 KB Output is correct
11 Correct 1134 ms 23544 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12544 KB Output is correct
2 Correct 3235 ms 108796 KB Output is correct
3 Correct 4002 ms 109696 KB Output is correct
4 Correct 3064 ms 106116 KB Output is correct
5 Correct 3436 ms 129544 KB Output is correct
6 Correct 4766 ms 112040 KB Output is correct
7 Correct 4105 ms 41660 KB Output is correct
8 Correct 3573 ms 40908 KB Output is correct
9 Correct 2855 ms 42860 KB Output is correct
10 Correct 4009 ms 40856 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 12800 KB Output is correct
2 Correct 1147 ms 23648 KB Output is correct
3 Correct 1167 ms 23532 KB Output is correct
4 Correct 1151 ms 23576 KB Output is correct
5 Correct 1216 ms 23644 KB Output is correct
6 Correct 991 ms 23596 KB Output is correct
7 Correct 1130 ms 23460 KB Output is correct
8 Correct 1123 ms 23688 KB Output is correct
9 Correct 1040 ms 23576 KB Output is correct
10 Correct 1014 ms 23516 KB Output is correct
11 Correct 1134 ms 23544 KB Output is correct
12 Correct 14 ms 12544 KB Output is correct
13 Correct 3235 ms 108796 KB Output is correct
14 Correct 4002 ms 109696 KB Output is correct
15 Correct 3064 ms 106116 KB Output is correct
16 Correct 3436 ms 129544 KB Output is correct
17 Correct 4766 ms 112040 KB Output is correct
18 Correct 4105 ms 41660 KB Output is correct
19 Correct 3573 ms 40908 KB Output is correct
20 Correct 2855 ms 42860 KB Output is correct
21 Correct 4009 ms 40856 KB Output is correct
22 Correct 5934 ms 107584 KB Output is correct
23 Correct 5542 ms 109920 KB Output is correct
24 Correct 5743 ms 110408 KB Output is correct
25 Correct 5908 ms 114152 KB Output is correct
26 Correct 7686 ms 110048 KB Output is correct
27 Correct 5977 ms 126960 KB Output is correct
28 Correct 5947 ms 108032 KB Output is correct
29 Execution timed out 8095 ms 109552 KB Time limit exceeded
30 Halted 0 ms 0 KB -