oj.uz

Submission #424489

# Submission time Handle Problem Language Result Execution time Memory
424489 2021-06-12T03:14:18 Z Osama_Alkhodairy Factories (JOI14_factories) C++17
100 / 100
 4725 ms 186928 KB 
#include <bits/stdc++.h>
#include "factories.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long
 
const int NN = 500001;
const int K = 20;
const ll INF = (ll)1e18;
 
int mark[NN], s[NN], e[NN], dep[NN], p[NN][K], dfstime;
ll d[NN], ans;
vector <pair <int, ll> > v[NN], g[NN];
 
void dfs(int node, int pnode){
    s[node] = dfstime++;
    p[node][0] = pnode;
    for(int i = 1 ; i < K ; i++){
        p[node][i] = p[p[node][i - 1]][i - 1];
    }
    for(auto &i : v[node]){
        if(i.first == pnode) continue;
        d[i.first] = d[node] + i.second;
        dep[i.first] = dep[node] + 1;
        dfs(i.first, node);
    }
    e[node] = dfstime - 1;
}
bool inside(int x, int y){
    return s[x] <= s[y] && e[y] <= e[x];
}
int lift(int x, int k){
    for(int i = 0 ; i < K ; i++){
        if((k >> i) & 1){
            x = p[x][i];
        }
    }
    return x;
}
int LCA(int x, int y){
    if(dep[x] >= dep[y]) swap(x, y);
    y = lift(y, dep[y] - dep[x]);
    if(x == y) return x;
    for(int i = K - 1 ; i >= 0 ; i--){
        if(p[x][i] != p[y][i]){
            x = p[x][i];
            y = p[y][i];
        }
    }
    return p[x][0];
}
pair <ll, ll> solve(int node, int pnode){
    pair <ll, ll> cur = make_pair(INF, INF);
    if(mark[node] == 1) cur.first = 0;
    if(mark[node] == 2) cur.second = 0;
    for(auto &i : g[node]){
        if(i.first == pnode) continue;
        auto f = solve(i.first, node);
        f.first += i.second;
        f.second += i.second;
        ans = min(ans, cur.first + f.second);
        ans = min(ans, cur.second + f.first);
        cur.first = min(cur.first, f.first);
        cur.second = min(cur.second, f.second);
    }
    return cur;
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0 ; i < N - 1 ; i++){
        v[A[i]].push_back(make_pair(B[i], D[i]));
        v[B[i]].push_back(make_pair(A[i], D[i]));
    }
    dfs(0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
    vector <int> all;
    for(int i = 0 ; i < S ; i++){
        mark[X[i]] = 1;
        all.push_back(X[i]);
    }
    for(int i = 0 ; i < T ; i++){
        mark[Y[i]] = 2;
        all.push_back(Y[i]);
    }
    sort(all.begin(), all.end(), [&](int l, int r){
        return s[l] < s[r];
    });
    int all_sz = all.size();
    for(int i = 0 ; i < all_sz ; i++){
        all.push_back(LCA(all[i], all[(i + 1) % all_sz]));
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    sort(all.begin(), all.end(), [&](int l, int r){
        return s[l] < s[r];
    });
    vector <int> cur;
    for(auto &i : all){
        while(cur.size() && !inside(cur.back(), i)) cur.pop_back();
        if(cur.size()){
            ll cost = d[i] - d[cur.back()];
            g[cur.back()].push_back(make_pair(i, cost));
            g[i].push_back(make_pair(cur.back(), cost));
        }
        cur.push_back(i);
    }
    ans = INF;
    solve(all[0], 0);
    for(auto &i : all){
        g[i].clear();
        mark[i] = 0;
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24140 KB Output is correct
2 Correct 1139 ms 33024 KB Output is correct
3 Correct 1165 ms 32988 KB Output is correct
4 Correct 1127 ms 33220 KB Output is correct
5 Correct 968 ms 33132 KB Output is correct
6 Correct 920 ms 32956 KB Output is correct
7 Correct 1173 ms 32888 KB Output is correct
8 Correct 1123 ms 33120 KB Output is correct
9 Correct 963 ms 33204 KB Output is correct
10 Correct 889 ms 32840 KB Output is correct
11 Correct 1183 ms 33040 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24032 KB Output is correct
2 Correct 2073 ms 127440 KB Output is correct
3 Correct 2512 ms 148328 KB Output is correct
4 Correct 1459 ms 142992 KB Output is correct
5 Correct 2801 ms 178244 KB Output is correct
6 Correct 2866 ms 150752 KB Output is correct
7 Correct 2343 ms 67700 KB Output is correct
8 Correct 1329 ms 67248 KB Output is correct
9 Correct 2375 ms 72960 KB Output is correct
10 Correct 2245 ms 69156 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24140 KB Output is correct
2 Correct 1139 ms 33024 KB Output is correct
3 Correct 1165 ms 32988 KB Output is correct
4 Correct 1127 ms 33220 KB Output is correct
5 Correct 968 ms 33132 KB Output is correct
6 Correct 920 ms 32956 KB Output is correct
7 Correct 1173 ms 32888 KB Output is correct
8 Correct 1123 ms 33120 KB Output is correct
9 Correct 963 ms 33204 KB Output is correct
10 Correct 889 ms 32840 KB Output is correct
11 Correct 1183 ms 33040 KB Output is correct
12 Correct 16 ms 24032 KB Output is correct
13 Correct 2073 ms 127440 KB Output is correct
14 Correct 2512 ms 148328 KB Output is correct
15 Correct 1459 ms 142992 KB Output is correct
16 Correct 2801 ms 178244 KB Output is correct
17 Correct 2866 ms 150752 KB Output is correct
18 Correct 2343 ms 67700 KB Output is correct
19 Correct 1329 ms 67248 KB Output is correct
20 Correct 2375 ms 72960 KB Output is correct
21 Correct 2245 ms 69156 KB Output is correct
22 Correct 3404 ms 162008 KB Output is correct
23 Correct 3274 ms 162732 KB Output is correct
24 Correct 3757 ms 165964 KB Output is correct
25 Correct 3943 ms 169068 KB Output is correct
26 Correct 4040 ms 160416 KB Output is correct
27 Correct 3697 ms 186928 KB Output is correct
28 Correct 2661 ms 157212 KB Output is correct
29 Correct 4725 ms 159152 KB Output is correct
30 Correct 4673 ms 158628 KB Output is correct
31 Correct 4583 ms 159064 KB Output is correct
32 Correct 2177 ms 75488 KB Output is correct
33 Correct 1540 ms 69900 KB Output is correct
34 Correct 2284 ms 66876 KB Output is correct
35 Correct 2132 ms 66440 KB Output is correct
36 Correct 2542 ms 67336 KB Output is correct
37 Correct 2476 ms 67164 KB Output is correct