oj.uz

Submission #285111

# Submission time Handle Problem Language Result Execution time Memory
285111 2020-08-28T10:23:24 Z BeanZ Factories (JOI14_factories) C++11
100 / 100
 7584 ms 245520 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], cur[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];
}
ll cs = 0;
void upd(ll u, ll root){
        //if (!ok[u]) recover.push_back(u), ok[u] = 1;
        if (u == 0) return;
        if (cur[u] != cs){
                cur[u] = cs;
                ans[u] = 1e15;
        }
        ans[u] = min(ans[u], dist(root, u));
        upd(par[u], root);
}
long long get(ll u, ll root){
        if (u == 0) return 1e15;
        if (cur[u] != cs){
                cur[u] = cs;
                ans[u] = 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();
        cs++;
        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;   }
                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;
                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:127:12: warning: unused variable 'root' [-Wunused-variable]
  127 |         ll root = findCT(1);
      |            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24576 KB Output is correct
2 Correct 656 ms 38716 KB Output is correct
3 Correct 913 ms 38860 KB Output is correct
4 Correct 798 ms 39288 KB Output is correct
5 Correct 911 ms 39412 KB Output is correct
6 Correct 396 ms 39400 KB Output is correct
7 Correct 772 ms 39288 KB Output is correct
8 Correct 813 ms 39372 KB Output is correct
9 Correct 1004 ms 39380 KB Output is correct
10 Correct 382 ms 39276 KB Output is correct
11 Correct 776 ms 39248 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 3165 ms 227532 KB Output is correct
3 Correct 4074 ms 231368 KB Output is correct
4 Correct 1136 ms 232768 KB Output is correct
5 Correct 5450 ms 245520 KB Output is correct
6 Correct 4284 ms 229984 KB Output is correct
7 Correct 2672 ms 71980 KB Output is correct
8 Correct 787 ms 73044 KB Output is correct
9 Correct 3056 ms 74840 KB Output is correct
10 Correct 3103 ms 73396 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24576 KB Output is correct
2 Correct 656 ms 38716 KB Output is correct
3 Correct 913 ms 38860 KB Output is correct
4 Correct 798 ms 39288 KB Output is correct
5 Correct 911 ms 39412 KB Output is correct
6 Correct 396 ms 39400 KB Output is correct
7 Correct 772 ms 39288 KB Output is correct
8 Correct 813 ms 39372 KB Output is correct
9 Correct 1004 ms 39380 KB Output is correct
10 Correct 382 ms 39276 KB Output is correct
11 Correct 776 ms 39248 KB Output is correct
12 Correct 18 ms 24192 KB Output is correct
13 Correct 3165 ms 227532 KB Output is correct
14 Correct 4074 ms 231368 KB Output is correct
15 Correct 1136 ms 232768 KB Output is correct
16 Correct 5450 ms 245520 KB Output is correct
17 Correct 4284 ms 229984 KB Output is correct
18 Correct 2672 ms 71980 KB Output is correct
19 Correct 787 ms 73044 KB Output is correct
20 Correct 3056 ms 74840 KB Output is correct
21 Correct 3103 ms 73396 KB Output is correct
22 Correct 4298 ms 229496 KB Output is correct
23 Correct 4837 ms 232212 KB Output is correct
24 Correct 6125 ms 231268 KB Output is correct
25 Correct 6367 ms 234360 KB Output is correct
26 Correct 5957 ms 231176 KB Output is correct
27 Correct 7584 ms 245240 KB Output is correct
28 Correct 1480 ms 232672 KB Output is correct
29 Correct 6089 ms 230380 KB Output is correct
30 Correct 6067 ms 230136 KB Output is correct
31 Correct 6077 ms 230432 KB Output is correct
32 Correct 3173 ms 74440 KB Output is correct
33 Correct 732 ms 72172 KB Output is correct
34 Correct 2041 ms 69148 KB Output is correct
35 Correct 2033 ms 69244 KB Output is correct
36 Correct 2527 ms 69496 KB Output is correct
37 Correct 2655 ms 69612 KB Output is correct