oj.uz

Submission #285040

# Submission time Handle Problem Language Result Execution time Memory
285040 2020-08-28T09:20:00 Z BeanZ Factories (JOI14_factories) C++14
33 / 100
 8000 ms 292280 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, ll S){
        initsz(u, u);
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : node[u]){
                if (in[j.first]) continue;
                if (sz[j.first] > sz[u]){
                        ll x = findCT(j.first, S - sz[u]);
                        par[x] = u;
                } else {
                        ll x = findCT(j.first, sz[j.first]);
                        par[x] = 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 = __lg(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, n);
        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:123:12: warning: unused variable 'root' [-Wunused-variable]
  123 |         ll root = findCT(1, n);
      |            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 750 ms 57080 KB Output is correct
3 Correct 898 ms 56952 KB Output is correct
4 Correct 900 ms 57208 KB Output is correct
5 Correct 937 ms 57464 KB Output is correct
6 Correct 424 ms 57084 KB Output is correct
7 Correct 882 ms 57132 KB Output is correct
8 Correct 947 ms 57080 KB Output is correct
9 Correct 962 ms 57340 KB Output is correct
10 Correct 430 ms 56968 KB Output is correct
11 Correct 879 ms 57080 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47616 KB Output is correct
2 Correct 3914 ms 261696 KB Output is correct
3 Correct 4976 ms 263756 KB Output is correct
4 Correct 1553 ms 264408 KB Output is correct
5 Correct 6387 ms 292280 KB Output is correct
6 Correct 5363 ms 265248 KB Output is correct
7 Correct 3579 ms 95604 KB Output is correct
8 Correct 1115 ms 96708 KB Output is correct
9 Correct 4403 ms 99896 KB Output is correct
10 Correct 3600 ms 96912 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47864 KB Output is correct
2 Correct 750 ms 57080 KB Output is correct
3 Correct 898 ms 56952 KB Output is correct
4 Correct 900 ms 57208 KB Output is correct
5 Correct 937 ms 57464 KB Output is correct
6 Correct 424 ms 57084 KB Output is correct
7 Correct 882 ms 57132 KB Output is correct
8 Correct 947 ms 57080 KB Output is correct
9 Correct 962 ms 57340 KB Output is correct
10 Correct 430 ms 56968 KB Output is correct
11 Correct 879 ms 57080 KB Output is correct
12 Correct 34 ms 47616 KB Output is correct
13 Correct 3914 ms 261696 KB Output is correct
14 Correct 4976 ms 263756 KB Output is correct
15 Correct 1553 ms 264408 KB Output is correct
16 Correct 6387 ms 292280 KB Output is correct
17 Correct 5363 ms 265248 KB Output is correct
18 Correct 3579 ms 95604 KB Output is correct
19 Correct 1115 ms 96708 KB Output is correct
20 Correct 4403 ms 99896 KB Output is correct
21 Correct 3600 ms 96912 KB Output is correct
22 Correct 5453 ms 263592 KB Output is correct
23 Correct 5599 ms 266116 KB Output is correct
24 Correct 7567 ms 265940 KB Output is correct
25 Correct 7653 ms 269468 KB Output is correct
26 Correct 7716 ms 266304 KB Output is correct
27 Execution timed out 8073 ms 287848 KB Time limit exceeded
28 Halted 0 ms 0 KB -