oj.uz

답안 #246880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246880 2020-07-10T13:22:37 Z receed 공장들 (JOI14_factories) C++14
33 / 100
 8000 ms 163328 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];
vector<int> cg[N];
int tin[N], tout[N], ct, up[L][N], th[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];
}

ll dfs2(int v) {
    ll ans = inf;
    for (int u : cg[v]) {
        ans = min(ans, dfs2(u));
        ll cd = h[u] - h[v];
        ans = min(ans, min(d1[v] + d2[u], d1[u] + d2[v]) + cd);
        d1[v] = min(d1[v], d1[u] + cd);
        d2[v] = min(d2[v], d2[u] + cd);
    }
    return ans;
}

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];});
    vector<int> st;
    for (int i : li) {
        if (st.empty())
            st.push_back(i);
        else {
            while (tout[st.back()] < tout[i])
                st.pop_back();
            if (st.back() == i)
                continue;
            assert(!st.empty());
            cg[st.back()].push_back(i);
            st.push_back(i);
        }
    }
    ll ans = dfs2(li[0]);
    for (int i : li) {
        cg[i].clear();
        d1[i] = d2[i] = inf;
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 24576 KB Output is correct
2 Correct 1313 ms 33760 KB Output is correct
3 Correct 1368 ms 33748 KB Output is correct
4 Correct 1295 ms 33968 KB Output is correct
5 Correct 1160 ms 42728 KB Output is correct
6 Correct 1137 ms 42360 KB Output is correct
7 Correct 1560 ms 42488 KB Output is correct
8 Correct 1284 ms 42680 KB Output is correct
9 Correct 1135 ms 42696 KB Output is correct
10 Correct 1138 ms 42360 KB Output is correct
11 Correct 1359 ms 42528 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 24192 KB Output is correct
2 Correct 3696 ms 118648 KB Output is correct
3 Correct 4750 ms 121336 KB Output is correct
4 Correct 3452 ms 129076 KB Output is correct
5 Correct 4306 ms 163328 KB Output is correct
6 Correct 5077 ms 135004 KB Output is correct
7 Correct 4519 ms 65248 KB Output is correct
8 Correct 4041 ms 65348 KB Output is correct
9 Correct 3297 ms 71564 KB Output is correct
10 Correct 4459 ms 67036 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 24576 KB Output is correct
2 Correct 1313 ms 33760 KB Output is correct
3 Correct 1368 ms 33748 KB Output is correct
4 Correct 1295 ms 33968 KB Output is correct
5 Correct 1160 ms 42728 KB Output is correct
6 Correct 1137 ms 42360 KB Output is correct
7 Correct 1560 ms 42488 KB Output is correct
8 Correct 1284 ms 42680 KB Output is correct
9 Correct 1135 ms 42696 KB Output is correct
10 Correct 1138 ms 42360 KB Output is correct
11 Correct 1359 ms 42528 KB Output is correct
12 Correct 22 ms 24192 KB Output is correct
13 Correct 3696 ms 118648 KB Output is correct
14 Correct 4750 ms 121336 KB Output is correct
15 Correct 3452 ms 129076 KB Output is correct
16 Correct 4306 ms 163328 KB Output is correct
17 Correct 5077 ms 135004 KB Output is correct
18 Correct 4519 ms 65248 KB Output is correct
19 Correct 4041 ms 65348 KB Output is correct
20 Correct 3297 ms 71564 KB Output is correct
21 Correct 4459 ms 67036 KB Output is correct
22 Correct 6413 ms 130952 KB Output is correct
23 Correct 6105 ms 132408 KB Output is correct
24 Correct 6677 ms 135484 KB Output is correct
25 Correct 6932 ms 137736 KB Output is correct
26 Execution timed out 8042 ms 129848 KB Time limit exceeded
27 Halted 0 ms 0 KB -