oj.uz

답안 #780007

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780007 2023-07-12T05:09:33 Z vjudge1 공장들 (JOI14_factories) C++17
100 / 100
 3490 ms 446896 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int lg2(unsigned long long i) { return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1; }
const int NM = 1e6+6;
vector<pair<int, long long>> g[NM];
vector<pair<int, long long>> g_aux[NM]; 
int t_in[NM];
int t_out[NM];
pair<int, int> sp[21][NM];
int up[21][NM];
long long up_dist[21][NM];
const long long INF = 1e18+5;
int n;
vector<pair<int, int>> euler_tour;
bool mark1[NM], mark2[NM], vis[NM];
long long res_query = INF;
long long dp1[NM], dp2[NM];
void dfs(int u, int p, int d){
    t_in[u] = euler_tour.size();
    up[0][u] = p;
    for (int i = 1; i <= 20; i++){
        up[i][u] = up[i - 1][up[i - 1][u]];
        up_dist[i][u] = up_dist[i - 1][u] + up_dist[i - 1][up[i - 1][u]];
    }
    euler_tour.push_back({d, u});
    for (auto& e : g[u]){
        int &v = e.first;
        long long &w = e.second;
        if (v == p) continue;
        up_dist[0][v] = w;
        dfs(v, u, d + 1);
        euler_tour.push_back({d, u});
    }
    t_out[u] = euler_tour.size() - 1;
}
inline void build_sparse_table(){
    for (int i = 0; i < (int)euler_tour.size(); i++){
        sp[0][i] = euler_tour[i];
    }
    for (int i = 1; i <= 20; i++){
        for (int j = 0; j < (int)euler_tour.size() - (1 << (i - 1)); j++){
            sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
        }
    }
}
inline pair<int, int> LCA(int u, int v){
    int l = t_in[u];
    int r = t_in[v];
    if (l > r) swap(l, r);
    int lvl = lg2(r - l + 1);
    return min(sp[lvl][l], sp[lvl][r - (1 << lvl) + 1]);
}
inline long long dist_to_ancestor(int u, int v){
    int dept = euler_tour[t_in[u]].first - euler_tour[t_in[v]].first;
    long long res = 0;
    for (int i = 20; i >= 0; i--){
        if ((dept >> i) & 1){
            res += up_dist[i][u];
            u = up[i][u];
        }
    }
    return res;
}


void dfs2(int u, int p){
    if (mark1[u]){
        dp1[u] = 0;
    }
    if (mark2[u]){
        dp2[u] = 0;
    }
    for (auto v : g_aux[u]){
        if (v.first == p) continue;
        dfs2(v.first, u);
        res_query = min(res_query, min(dp1[u] + dp2[v.first] + v.second, dp2[u] + dp1[v.first]+ v.second));
        dp1[u] = min(dp1[u], dp1[v.first] + v.second);
        dp2[u] = min(dp2[u], dp2[v.first] + v.second);
    }
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < N; i++){
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0, 0);
    build_sparse_table();
    fill(begin(dp1), end(dp1), INF);
    fill(begin(dp2), end(dp2), INF);

}
long long Query(int S, int X[], int T, int Y[]) {
    res_query = INF;
    vector<int> a;
    for (int i = 0; i < S; i++){
        a.push_back(X[i]);
        mark1[X[i]] = 1;
        vis[X[i]] = 1;
    }
    for (int i = 0; i < T; i++){
        mark2[Y[i]] = 1;
        if (!vis[Y[i]]){
            a.push_back(Y[i]);
            vis[Y[i]] = 1;
        }
    }
    sort(a.begin(), a.end(), [&](const int &x, const int &y){
            return t_in[x] < t_in[y];
            });
    for (int i = 0; i < S + T - 1; i ++){
        int lca = LCA(a[i], a[i + 1]).second;
        if (!vis[lca]){
            a.push_back(lca);
            vis[lca] = 1;
        }
    }
    sort(a.begin(), a.end(), [&](const int &x, const int &y){
            return t_in[x] < t_in[y];
            });
    stack<int> st;
    for (int i = 0; i < int(a.size()); i++){
        while(!st.empty() && t_out[st.top()] <= t_in[a[i]]){
            st.pop();
        }
        if (st.empty()){
            st.push(a[i]);
            continue;
        }
        int u = st.top();
        if (u != a[i]){
            long long w = dist_to_ancestor(a[i], u);
            g_aux[u].push_back({a[i], w});
        }
        st.push(a[i]);
    }
    dfs2(a[0], -1);
    for (auto& i : a){
        dp1[i] = dp2[i] = INF;
        mark1[i] = mark2[i] = vis[i] = 0;
        g_aux[i].clear();
    }
    return res_query;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 63828 KB Output is correct
2 Correct 536 ms 74304 KB Output is correct
3 Correct 609 ms 74464 KB Output is correct
4 Correct 560 ms 74316 KB Output is correct
5 Correct 498 ms 74660 KB Output is correct
6 Correct 435 ms 74184 KB Output is correct
7 Correct 610 ms 74248 KB Output is correct
8 Correct 575 ms 74316 KB Output is correct
9 Correct 515 ms 74664 KB Output is correct
10 Correct 432 ms 74184 KB Output is correct
11 Correct 607 ms 74188 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 63732 KB Output is correct
2 Correct 1466 ms 394560 KB Output is correct
3 Correct 2199 ms 401076 KB Output is correct
4 Correct 1123 ms 392336 KB Output is correct
5 Correct 2380 ms 446896 KB Output is correct
6 Correct 2263 ms 402056 KB Output is correct
7 Correct 1432 ms 135744 KB Output is correct
8 Correct 608 ms 134664 KB Output is correct
9 Correct 1400 ms 143148 KB Output is correct
10 Correct 1480 ms 136848 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 63828 KB Output is correct
2 Correct 536 ms 74304 KB Output is correct
3 Correct 609 ms 74464 KB Output is correct
4 Correct 560 ms 74316 KB Output is correct
5 Correct 498 ms 74660 KB Output is correct
6 Correct 435 ms 74184 KB Output is correct
7 Correct 610 ms 74248 KB Output is correct
8 Correct 575 ms 74316 KB Output is correct
9 Correct 515 ms 74664 KB Output is correct
10 Correct 432 ms 74184 KB Output is correct
11 Correct 607 ms 74188 KB Output is correct
12 Correct 32 ms 63732 KB Output is correct
13 Correct 1466 ms 394560 KB Output is correct
14 Correct 2199 ms 401076 KB Output is correct
15 Correct 1123 ms 392336 KB Output is correct
16 Correct 2380 ms 446896 KB Output is correct
17 Correct 2263 ms 402056 KB Output is correct
18 Correct 1432 ms 135744 KB Output is correct
19 Correct 608 ms 134664 KB Output is correct
20 Correct 1400 ms 143148 KB Output is correct
21 Correct 1480 ms 136848 KB Output is correct
22 Correct 2286 ms 405220 KB Output is correct
23 Correct 2509 ms 405848 KB Output is correct
24 Correct 3037 ms 411092 KB Output is correct
25 Correct 3103 ms 414440 KB Output is correct
26 Correct 3403 ms 404524 KB Output is correct
27 Correct 3136 ms 445308 KB Output is correct
28 Correct 1794 ms 400220 KB Output is correct
29 Correct 3401 ms 403104 KB Output is correct
30 Correct 3427 ms 402340 KB Output is correct
31 Correct 3490 ms 402940 KB Output is correct
32 Correct 1138 ms 145712 KB Output is correct
33 Correct 810 ms 137544 KB Output is correct
34 Correct 1083 ms 134688 KB Output is correct
35 Correct 1044 ms 134468 KB Output is correct
36 Correct 1417 ms 135656 KB Output is correct
37 Correct 1358 ms 135480 KB Output is correct