oj.uz

Submission #285080

# Submission time Handle Problem Language Result Execution time Memory
285080 2020-08-28T09:54:12 Z BeanZ Factories (JOI14_factories) C++14
100 / 100
 7380 ms 241356 KB 
#include <bits/stdc++.h>
#include "factories.h"


using namespace std;

#define ll int
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lg = 19;
vector<pair<ll, ll>> node[N];
ll dep[N], tin[N];
long long dis[N];
ll sz[N];
ll par[N], st[N];
long long ans[N];
bool ok[N], in[N];
ll timer = 0;
pair<ll, ll> dp[20][N * 2];
void dfs(ll u, ll p){
        st[u] = ++timer;
        tin[timer] = u;
        for (auto j : node[u]){
                if (j.first == p) continue;
                dis[j.first] = dis[u] + j.second;
                dep[j.first] = dep[u] + 1;
                dfs(j.first, u);
                tin[++timer] = u;
        }
}
void buildLCA(){
        for (int i = 1; i <= timer; i++) dp[0][i] = {dep[tin[i]], tin[i]};
        for (int i = 1; i <= lg; i++){
                for (int j = 1; j <= timer; j++){
                        if ((j + (1 << i)) > timer) break;
                        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
                }
        }
}
ll findnewCT(ll u, ll p, ll S){
        for (auto j : node[u]){
                if (j.first == p || in[j.first]) continue;
                if ((sz[j.first] * 2) > S) return findnewCT(j.first, u, S);
        }
        return u;
}
ll initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : node[u]){
                if (j.first == p || in[j.first]) continue;
                sz[u] += initsz(j.first, u);;
        }
        return sz[u];
}
ll findCT(ll u){
        ll S = initsz(u, u);
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : node[u]){
                if (in[j.first]) continue;
                par[findCT(j.first)] = u;
        }
        return u;
}
ll LCA(ll u, ll v){
        ll l = st[u], r = st[v];
        if (l > r) swap(l, r);
        ll k = 31 - __builtin_clz(r - l + 1);
        return min(dp[k][l], dp[k][r - (1 << k) + 1]).second;
}
long long dist(ll u, ll v){
        ll lca = LCA(u, v);
        return dis[u] + dis[v] - 2 * dis[lca];
}
//vector<ll> recover;
void upd(ll u, ll root){
        //if (!ok[u]) recover.push_back(u), ok[u] = 1;
        if (u == 0) return;
        ans[u] = min(ans[u], dist(root, u));
        upd(par[u], root);
}
long long get(ll u, ll root){
        if (u == 0) return 1e15;
        return min(ans[u] + dist(u, root), get(par[u], root));
}
long long Query(int S, int X[], int T, int Y[]){
        //recover.clear();
        if (S > T){
                for (int i = 1; i <= T; i++){
                        upd(Y[i - 1] + 1, Y[i - 1] + 1);
                }
                long long res = 1e15;
                for (int i = 1; i <= S; i++){
                        res = min(res, get(X[i - 1] + 1, X[i - 1] + 1));
                }
                //for (auto j : recover) ans[j] = 1e18, ok[j] = 0;
                for (int i = 1; i <= T; i++){
                        ll now = Y[i - 1] + 1;
                        while (now){
                                ans[now] = 1e15;
                                now = par[now];
                        }
                }
                return res;
        } else {
                for (int i = 1; i <= S; i++){
                        upd(X[i - 1] + 1, X[i - 1] + 1);
                }
                long long res = 1e15;
                for (int i = 1; i <= T; i++){
                        res = min(res, get(Y[i - 1] + 1, Y[i - 1] + 1));
                }
                //for (auto j : recover) ans[j] = 1e18, ok[j] = 0;
                for (int i = 1; i <= S; i++){
                        ll now = X[i - 1] + 1;
                        while (now){
                                ans[now] = 1e15;
                                now = par[now];
                        }
                }
                return res;
        }
}
void Init(int n, int A[], int B[], int D[]){
        for (int i = 1; i < n; i++){
                node[A[i - 1] + 1].push_back({B[i - 1] + 1, D[i - 1]});
                node[B[i - 1] + 1].push_back({A[i - 1] + 1, D[i - 1]});
        }
        dfs(1, 1);
        buildLCA();
        ll root = findCT(1);
        for (int i = 1; i <= n; i++) ans[i] = 1e15;
}
/*
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
}
*/
/*
*/

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:132:12: warning: unused variable 'root' [-Wunused-variable]
  132 |         ll root = findCT(1);
      |            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24320 KB Output is correct
2 Correct 631 ms 33444 KB Output is correct
3 Correct 786 ms 33528 KB Output is correct
4 Correct 726 ms 33400 KB Output is correct
5 Correct 848 ms 33664 KB Output is correct
6 Correct 324 ms 33400 KB Output is correct
7 Correct 729 ms 33528 KB Output is correct
8 Correct 733 ms 33528 KB Output is correct
9 Correct 791 ms 33592 KB Output is correct
10 Correct 328 ms 33400 KB Output is correct
11 Correct 715 ms 33528 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24192 KB Output is correct
2 Correct 2976 ms 223952 KB Output is correct
3 Correct 3863 ms 224864 KB Output is correct
4 Correct 1030 ms 224720 KB Output is correct
5 Correct 5241 ms 241356 KB Output is correct
6 Correct 4169 ms 226136 KB Output is correct
7 Correct 2629 ms 68692 KB Output is correct
8 Correct 635 ms 69612 KB Output is correct
9 Correct 2936 ms 71712 KB Output is correct
10 Correct 2568 ms 70008 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24320 KB Output is correct
2 Correct 631 ms 33444 KB Output is correct
3 Correct 786 ms 33528 KB Output is correct
4 Correct 726 ms 33400 KB Output is correct
5 Correct 848 ms 33664 KB Output is correct
6 Correct 324 ms 33400 KB Output is correct
7 Correct 729 ms 33528 KB Output is correct
8 Correct 733 ms 33528 KB Output is correct
9 Correct 791 ms 33592 KB Output is correct
10 Correct 328 ms 33400 KB Output is correct
11 Correct 715 ms 33528 KB Output is correct
12 Correct 18 ms 24192 KB Output is correct
13 Correct 2976 ms 223952 KB Output is correct
14 Correct 3863 ms 224864 KB Output is correct
15 Correct 1030 ms 224720 KB Output is correct
16 Correct 5241 ms 241356 KB Output is correct
17 Correct 4169 ms 226136 KB Output is correct
18 Correct 2629 ms 68692 KB Output is correct
19 Correct 635 ms 69612 KB Output is correct
20 Correct 2936 ms 71712 KB Output is correct
21 Correct 2568 ms 70008 KB Output is correct
22 Correct 4204 ms 225524 KB Output is correct
23 Correct 4422 ms 227864 KB Output is correct
24 Correct 6316 ms 226700 KB Output is correct
25 Correct 6171 ms 230392 KB Output is correct
26 Correct 5996 ms 227064 KB Output is correct
27 Correct 7380 ms 241272 KB Output is correct
28 Correct 1426 ms 230876 KB Output is correct
29 Correct 5803 ms 228732 KB Output is correct
30 Correct 5816 ms 228580 KB Output is correct
31 Correct 5876 ms 228856 KB Output is correct
32 Correct 3092 ms 86264 KB Output is correct
33 Correct 638 ms 83944 KB Output is correct
34 Correct 1923 ms 80632 KB Output is correct
35 Correct 1868 ms 80632 KB Output is correct
36 Correct 2454 ms 80876 KB Output is correct
37 Correct 2444 ms 80896 KB Output is correct