oj.uz

Submission #491720

# Submission time Handle Problem Language Result Execution time Memory
491720 2021-12-04T02:55:11 Z truc12a2cvp Factories (JOI14_factories) C++14
100 / 100
 6214 ms 405984 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> II;
const int N = 5e5 + 3;
const int logN = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int n, child[N], a[N], b[N], d[N], q, f[N][logN], depth[N], x[N], y[N], s, t;
bool ers[N];
vector<II> g[N], par[N];
ll dist[N], root_dis[N];

void Dfs(int u = 1, int p = 0, int di = 0){
       depth[u] = depth[p] + 1;
       root_dis[u] = root_dis[p] + di;
       f[u][0] = p;
       for(int i = 1; i < logN; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
       for(auto x : g[u]){
              int v = x.second, uv = x.first;
              if(v == p) continue;
              Dfs(v, u, uv);
       }
}

int lca(int u, int v) {
       if(depth[u] < depth[v]) swap(u, v);
       for(int i = logN - 1; i >= 0; i --){
              if(depth[f[u][i]] >= depth[v]) u = f[u][i];
       }
       if(u == v) return u;
       for(int i = logN - 1; i >= 0; i --){
              if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
       }
       return f[u][0];
}

inline ll get_dist(int u, int v){
       return root_dis[u] + root_dis[v] - 2 * root_dis[lca(u, v)];
}

int dfs(int u, int p = 0){
       child[u] = 1;
       for(auto x : g[u]){
              int v = x.second;
              if(v != p && !ers[v]) child[u] += dfs(v, u);
       }
       return child[u];
}

int get_centroid(int u, int sz, int p = 0){
       for(auto x : g[u]){
              int v = x.second;
              if(!ers[v] && v != p && child[v] * 2 > sz) return get_centroid(v, sz, u);
       }
       return u;
}

void centroid(int u = 1, int p = 0){
       int cen = get_centroid(u, dfs(u));
       for(auto x : par[p]) par[cen].push_back(II(x.first, get_dist(cen, x.first)));
       par[cen].push_back(II(cen, 0));
       ers[cen] = true;
       for(auto x : g[cen]){
              int v = x.second;
              if(!ers[v]) centroid(v, cen);
       }
}

void Init(int N, int A[], int B[], int D[]){
       n = N;
       for(int i = 1; i <= n; i ++) dist[i] = INF, g[i].clear();
       for(int i = 0; i <= n - 2; i ++){
              A[i] ++;
              B[i] ++;
              g[A[i]].push_back(II(D[i], B[i]));
              g[B[i]].push_back(II(D[i], A[i]));
       }
       Dfs();
       centroid();
}

ll Query(int S, int X[], int T, int Y[]){
       for(int i = 0; i < S; i ++){
              X[i] ++;
              for(auto x : par[X[i]]) dist[x.first] = min(dist[x.first], x.second);
       }

       ll ans = INF;
       for(int i = 0; i < T; i ++){
              Y[i] ++;
              for(auto x : par[Y[i]]) ans = min(ans, dist[x.first] + x.second);
       }
       for(int i = 0; i < S; i ++){
              for(auto x : par[X[i]]) dist[x.first] = INF;
       }
       return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24396 KB Output is correct
2 Correct 268 ms 42768 KB Output is correct
3 Correct 290 ms 43260 KB Output is correct
4 Correct 293 ms 43288 KB Output is correct
5 Correct 306 ms 43680 KB Output is correct
6 Correct 224 ms 42296 KB Output is correct
7 Correct 284 ms 43244 KB Output is correct
8 Correct 292 ms 43332 KB Output is correct
9 Correct 324 ms 43592 KB Output is correct
10 Correct 213 ms 42308 KB Output is correct
11 Correct 301 ms 43376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24012 KB Output is correct
2 Correct 2338 ms 256524 KB Output is correct
3 Correct 3781 ms 324364 KB Output is correct
4 Correct 962 ms 153032 KB Output is correct
5 Correct 5328 ms 401796 KB Output is correct
6 Correct 3925 ms 325836 KB Output is correct
7 Correct 1082 ms 90864 KB Output is correct
8 Correct 391 ms 68844 KB Output is correct
9 Correct 1277 ms 103600 KB Output is correct
10 Correct 1103 ms 92332 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24396 KB Output is correct
2 Correct 268 ms 42768 KB Output is correct
3 Correct 290 ms 43260 KB Output is correct
4 Correct 293 ms 43288 KB Output is correct
5 Correct 306 ms 43680 KB Output is correct
6 Correct 224 ms 42296 KB Output is correct
7 Correct 284 ms 43244 KB Output is correct
8 Correct 292 ms 43332 KB Output is correct
9 Correct 324 ms 43592 KB Output is correct
10 Correct 213 ms 42308 KB Output is correct
11 Correct 301 ms 43376 KB Output is correct
12 Correct 15 ms 24012 KB Output is correct
13 Correct 2338 ms 256524 KB Output is correct
14 Correct 3781 ms 324364 KB Output is correct
15 Correct 962 ms 153032 KB Output is correct
16 Correct 5328 ms 401796 KB Output is correct
17 Correct 3925 ms 325836 KB Output is correct
18 Correct 1082 ms 90864 KB Output is correct
19 Correct 391 ms 68844 KB Output is correct
20 Correct 1277 ms 103600 KB Output is correct
21 Correct 1103 ms 92332 KB Output is correct
22 Correct 2803 ms 261832 KB Output is correct
23 Correct 2797 ms 266700 KB Output is correct
24 Correct 4432 ms 332040 KB Output is correct
25 Correct 4420 ms 336352 KB Output is correct
26 Correct 4438 ms 333324 KB Output is correct
27 Correct 6214 ms 405984 KB Output is correct
28 Correct 1308 ms 163464 KB Output is correct
29 Correct 4343 ms 332124 KB Output is correct
30 Correct 4390 ms 331772 KB Output is correct
31 Correct 4331 ms 332464 KB Output is correct
32 Correct 1430 ms 104504 KB Output is correct
33 Correct 483 ms 69304 KB Output is correct
34 Correct 843 ms 83948 KB Output is correct
35 Correct 850 ms 84696 KB Output is correct
36 Correct 1127 ms 89288 KB Output is correct
37 Correct 1118 ms 89120 KB Output is correct