oj.uz

Submission #284932

# Submission time Handle Problem Language Result Execution time Memory
284932 2020-08-28T08:09:54 Z BeanZ Factories (JOI14_factories) C++14
15 / 100
 8000 ms 151100 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];
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 (auto j : node[u]){
                if (j.first == p) continue;
                dp[j.first][0] = u;
                dis[j.first] = dis[u] + 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 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 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:112:12: warning: unused variable 'root' [-Wunused-variable]
  112 |         ll root = findCT(1, n);
      |            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 47744 KB Output is correct
2 Correct 1282 ms 56312 KB Output is correct
3 Correct 2181 ms 56312 KB Output is correct
4 Correct 2071 ms 56364 KB Output is correct
5 Correct 2292 ms 56696 KB Output is correct
6 Correct 505 ms 56368 KB Output is correct
7 Correct 2089 ms 56448 KB Output is correct
8 Correct 2225 ms 56572 KB Output is correct
9 Correct 2262 ms 56824 KB Output is correct
10 Correct 490 ms 56312 KB Output is correct
11 Correct 2099 ms 56580 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47488 KB Output is correct
2 Correct 4429 ms 150844 KB Output is correct
3 Execution timed out 8105 ms 151100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 47744 KB Output is correct
2 Correct 1282 ms 56312 KB Output is correct
3 Correct 2181 ms 56312 KB Output is correct
4 Correct 2071 ms 56364 KB Output is correct
5 Correct 2292 ms 56696 KB Output is correct
6 Correct 505 ms 56368 KB Output is correct
7 Correct 2089 ms 56448 KB Output is correct
8 Correct 2225 ms 56572 KB Output is correct
9 Correct 2262 ms 56824 KB Output is correct
10 Correct 490 ms 56312 KB Output is correct
11 Correct 2099 ms 56580 KB Output is correct
12 Correct 36 ms 47488 KB Output is correct
13 Correct 4429 ms 150844 KB Output is correct
14 Execution timed out 8105 ms 151100 KB Time limit exceeded
15 Halted 0 ms 0 KB -