oj.uz

Submission #285067

# Submission time Handle Problem Language Result Execution time Memory
285067 2020-08-28T09:43:31 Z BeanZ Factories (JOI14_factories) C++14
33 / 100
 8000 ms 291996 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];
long long ans[N];
bool ok[N], in[N];
vector<ll> idx[N];
ll timer = 0;
pair<ll, ll> dp[20][N * 2];
void dfs(ll u, ll p){
        timer++;
        idx[u].push_back(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);
                timer++;
                tin[timer] = u;
                idx[u].push_back(timer);
        }
}
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;
}
void initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : node[u]){
                if (j.first == p || in[j.first]) continue;
                initsz(j.first, u);
                sz[u] += sz[j.first];
        }
}
ll findCT(ll u){
        initsz(u, u);
        ll S = sz[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 = idx[u][0], r = idx[v][0];
        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();
        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;
}
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:118:12: warning: unused variable 'root' [-Wunused-variable]
  118 |         ll root = findCT(1);
      |            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47872 KB Output is correct
2 Correct 716 ms 57200 KB Output is correct
3 Correct 889 ms 57012 KB Output is correct
4 Correct 878 ms 56952 KB Output is correct
5 Correct 923 ms 57464 KB Output is correct
6 Correct 407 ms 57080 KB Output is correct
7 Correct 848 ms 56952 KB Output is correct
8 Correct 916 ms 57080 KB Output is correct
9 Correct 995 ms 57340 KB Output is correct
10 Correct 389 ms 57080 KB Output is correct
11 Correct 874 ms 56952 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47616 KB Output is correct
2 Correct 3622 ms 261692 KB Output is correct
3 Correct 4678 ms 263484 KB Output is correct
4 Correct 1409 ms 263880 KB Output is correct
5 Correct 6080 ms 291996 KB Output is correct
6 Correct 4844 ms 264932 KB Output is correct
7 Correct 3503 ms 95416 KB Output is correct
8 Correct 1064 ms 96540 KB Output is correct
9 Correct 4035 ms 99768 KB Output is correct
10 Correct 3513 ms 96840 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47872 KB Output is correct
2 Correct 716 ms 57200 KB Output is correct
3 Correct 889 ms 57012 KB Output is correct
4 Correct 878 ms 56952 KB Output is correct
5 Correct 923 ms 57464 KB Output is correct
6 Correct 407 ms 57080 KB Output is correct
7 Correct 848 ms 56952 KB Output is correct
8 Correct 916 ms 57080 KB Output is correct
9 Correct 995 ms 57340 KB Output is correct
10 Correct 389 ms 57080 KB Output is correct
11 Correct 874 ms 56952 KB Output is correct
12 Correct 35 ms 47616 KB Output is correct
13 Correct 3622 ms 261692 KB Output is correct
14 Correct 4678 ms 263484 KB Output is correct
15 Correct 1409 ms 263880 KB Output is correct
16 Correct 6080 ms 291996 KB Output is correct
17 Correct 4844 ms 264932 KB Output is correct
18 Correct 3503 ms 95416 KB Output is correct
19 Correct 1064 ms 96540 KB Output is correct
20 Correct 4035 ms 99768 KB Output is correct
21 Correct 3513 ms 96840 KB Output is correct
22 Correct 5369 ms 263384 KB Output is correct
23 Correct 5477 ms 265916 KB Output is correct
24 Correct 7320 ms 265484 KB Output is correct
25 Correct 7241 ms 268988 KB Output is correct
26 Correct 7845 ms 265620 KB Output is correct
27 Execution timed out 8106 ms 287596 KB Time limit exceeded
28 Halted 0 ms 0 KB -