oj.uz

Submission #284928

# Submission time Handle Problem Language Result Execution time Memory
284928 2020-08-28T08:05:23 Z BeanZ Factories (JOI14_factories) C++14
15 / 100
 8000 ms 229184 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 = 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];
        long long 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 77 ms 47736 KB Output is correct
2 Correct 2272 ms 57340 KB Output is correct
3 Correct 3797 ms 57240 KB Output is correct
4 Correct 3727 ms 57216 KB Output is correct
5 Correct 4448 ms 57464 KB Output is correct
6 Correct 819 ms 57212 KB Output is correct
7 Correct 3734 ms 57208 KB Output is correct
8 Correct 3925 ms 57208 KB Output is correct
9 Correct 4452 ms 57336 KB Output is correct
10 Correct 823 ms 57208 KB Output is correct
11 Correct 3773 ms 57208 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47616 KB Output is correct
2 Correct 6248 ms 229180 KB Output is correct
3 Execution timed out 8106 ms 229184 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 47736 KB Output is correct
2 Correct 2272 ms 57340 KB Output is correct
3 Correct 3797 ms 57240 KB Output is correct
4 Correct 3727 ms 57216 KB Output is correct
5 Correct 4448 ms 57464 KB Output is correct
6 Correct 819 ms 57212 KB Output is correct
7 Correct 3734 ms 57208 KB Output is correct
8 Correct 3925 ms 57208 KB Output is correct
9 Correct 4452 ms 57336 KB Output is correct
10 Correct 823 ms 57208 KB Output is correct
11 Correct 3773 ms 57208 KB Output is correct
12 Correct 38 ms 47616 KB Output is correct
13 Correct 6248 ms 229180 KB Output is correct
14 Execution timed out 8106 ms 229184 KB Time limit exceeded
15 Halted 0 ms 0 KB -