oj.uz

Submission #284925

# Submission time Handle Problem Language Result Execution time Memory
284925 2020-08-28T08:02:42 Z BeanZ Factories (JOI14_factories) C++14
15 / 100
 8000 ms 286664 KB 
#include <bits/stdc++.h>
#include "factories.h"


using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lg = 20;
vector<pair<ll, ll>> node[N];
vector<ll> adj[N];
ll dp[N][21], dep[N];
long long dis[N][21];
ll sz[N];
ll par[N];
long long ans[N];
ll a[N];
bool ok[N], in[N];
void dfs(ll u, ll p){
        for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
        for (int i = 1; i <= lg; i++) dis[u][i] = dis[dp[u][i - 1]][i - 1] + dis[u][i - 1];
        for (auto j : node[u]){
                if (j.first == p) continue;
                dp[j.first][0] = u;
                dis[j.first][0] = j.second;
                dep[j.first] = dep[u] + 1;
                dfs(j.first, u);
        }
}
ll findnewCT(ll u, ll p, ll S){
        for (auto j : adj[u]){
                if (j == p || in[j]) continue;
                if ((sz[j] * 2) >= S) return findnewCT(j, u, S);
        }
        return u;
}
void initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : adj[u]){
                if (j == p || in[j]) continue;
                initsz(j, u);
                sz[u] += sz[j];
        }
}
ll findCT(ll u, ll S){
        initsz(u, u);
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : adj[u]){
                if (in[j]) continue;
                if (sz[j] > sz[u]){
                        ll x = findCT(j, S - sz[u]);
                        par[x] = u;
                } else {
                        ll x = findCT(j, sz[j]);
                        par[x] = u;
                }
        }
        return u;
}
ll LCA(ll u, ll v){
        if (dep[u] > dep[v]) swap(u, v);
        ll dist = dep[v] - dep[u];
        for (int i = lg; i >= 0; i--){
                if (dist & (1 << i)) v = dp[v][i];
        }
        if (u == v) return u;
        for (int i = lg; i >= 0; i--){
                if (dp[u][i] != dp[v][i]){
                        u = dp[u][i];
                        v = dp[v][i];
                }
        }
        return dp[u][0];
}
long long cal(ll u, ll lca){
        ll dist = dep[u] - dep[lca];
        ll res = 0;
        for (int i = lg; i >= 0; i--){
                if (dist & (1 << i)){
                        res += dis[u][i];
                        u = dp[u][i];
                }
        }
        return res;
}
long long dist(ll u, ll v){
        ll lca = LCA(u, v);
        return cal(u, lca) + cal(v, 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 1e16;
        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 = 1e18;
        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;
}
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]});
                adj[A[i - 1] + 1].push_back(B[i - 1] + 1);
                adj[B[i - 1] + 1].push_back(A[i - 1] + 1);
        }
        dfs(1, 1);
        ll root = findCT(1, n);
        for (int i = 1; i <= n; i++) ans[i] = 1e18;
}
/*
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:124:12: warning: unused variable 'root' [-Wunused-variable]
  124 |         ll root = findCT(1, n);
      |            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 48120 KB Output is correct
2 Correct 2459 ms 58744 KB Output is correct
3 Correct 4328 ms 58872 KB Output is correct
4 Correct 4146 ms 58744 KB Output is correct
5 Correct 4646 ms 59040 KB Output is correct
6 Correct 875 ms 58860 KB Output is correct
7 Correct 4225 ms 58616 KB Output is correct
8 Correct 4265 ms 58912 KB Output is correct
9 Correct 4740 ms 58852 KB Output is correct
10 Correct 821 ms 58732 KB Output is correct
11 Correct 4140 ms 58868 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47744 KB Output is correct
2 Correct 6354 ms 286424 KB Output is correct
3 Execution timed out 8035 ms 286664 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 48120 KB Output is correct
2 Correct 2459 ms 58744 KB Output is correct
3 Correct 4328 ms 58872 KB Output is correct
4 Correct 4146 ms 58744 KB Output is correct
5 Correct 4646 ms 59040 KB Output is correct
6 Correct 875 ms 58860 KB Output is correct
7 Correct 4225 ms 58616 KB Output is correct
8 Correct 4265 ms 58912 KB Output is correct
9 Correct 4740 ms 58852 KB Output is correct
10 Correct 821 ms 58732 KB Output is correct
11 Correct 4140 ms 58868 KB Output is correct
12 Correct 38 ms 47744 KB Output is correct
13 Correct 6354 ms 286424 KB Output is correct
14 Execution timed out 8035 ms 286664 KB Time limit exceeded
15 Halted 0 ms 0 KB -