oj.uz

Submission #854449

# Submission time Handle Problem Language Result Execution time Memory
854449 2023-09-27T16:43:27 Z gun_gan Factories (JOI14_factories) C++17
100 / 100
 3699 ms 384656 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MX = 5e5 + 5;
 
int N, Q;
 
ll sz[MX], ans[MX];
bool removed[MX];
 
vector<pair<int,int>> g[MX];
 
int getSize(int v, int p) {
      sz[v] = 1;
      for(auto [u, w] : g[v]) {
            if(u == p || removed[u]) continue; 
            sz[v] += getSize(u, v);
      }
      return sz[v];
}
 
int getCentroid(int v, int p, int size) {
      for(auto [u, w] : g[v]) {
            if(u != p && sz[u] > size / 2 && !removed[u]) {
                  return getCentroid(u, v, size);
            }
      }
 
      return v;
}
 
vector<pair<ll,ll>> ancestors[MX];
 
void getDists(int v, int centroid, int p, ll curDist) {
      for(auto [u, w] : g[v]) {
            if(u == p || removed[u]) continue;
            getDists(u, centroid, v, curDist + w); 
      }
 
      ancestors[v].push_back({centroid, curDist});
}
 
void build(int v) {
      int centroid = getCentroid(v, -1, getSize(v, -1));
 
      for(auto [u, w] : g[centroid]) {
            if(removed[u]) continue;
            getDists(u, centroid, centroid, w);
      }
 
      removed[centroid] = 1;
 
      for(auto [u, w] : g[centroid]) {
            if(removed[u]) continue;
            build(u);
      }
}
 
void Init(int _N, int A[], int B[], int D[]) {
      N = _N;
      for(int i = 0; i < N - 1; i++) {
            g[A[i]].push_back({B[i], D[i]});
            g[B[i]].push_back({A[i], D[i]});
      }
      for(int i = 0; i < N; i++) ans[i] = 1e18;
 
      build(0);
      for(int i = 0; i < N; i++) ancestors[i].push_back({i, 0});
}
 
long long Query(int s, int X[], int t, int Y[]) {
      vector<int> R;
      for(int i = 0; i < s; i++) {
            int x = X[i];
 
            for(auto [y, d] : ancestors[x]) {
                  R.push_back(y);
                  ans[y] = min(ans[y], d);
            }
      }
 
      ll res = 1e18;
      for(int i = 0; i < t; i++) {
            int x = Y[i];
 
            for(auto [y, d] : ancestors[x]) {
                  res = min(res, d + ans[y]);
            }
      }
 
      for(auto x : R) ans[x] = 1e18;
 
      return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 193 ms 50848 KB Output is correct
3 Correct 221 ms 51280 KB Output is correct
4 Correct 235 ms 61200 KB Output is correct
5 Correct 250 ms 61304 KB Output is correct
6 Correct 158 ms 59728 KB Output is correct
7 Correct 224 ms 61016 KB Output is correct
8 Correct 223 ms 60756 KB Output is correct
9 Correct 219 ms 61300 KB Output is correct
10 Correct 165 ms 59920 KB Output is correct
11 Correct 221 ms 60808 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 45656 KB Output is correct
2 Correct 1722 ms 206448 KB Output is correct
3 Correct 2558 ms 289308 KB Output is correct
4 Correct 655 ms 121180 KB Output is correct
5 Correct 3372 ms 372476 KB Output is correct
6 Correct 2624 ms 307580 KB Output is correct
7 Correct 737 ms 96100 KB Output is correct
8 Correct 324 ms 74052 KB Output is correct
9 Correct 835 ms 111272 KB Output is correct
10 Correct 756 ms 96904 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 193 ms 50848 KB Output is correct
3 Correct 221 ms 51280 KB Output is correct
4 Correct 235 ms 61200 KB Output is correct
5 Correct 250 ms 61304 KB Output is correct
6 Correct 158 ms 59728 KB Output is correct
7 Correct 224 ms 61016 KB Output is correct
8 Correct 223 ms 60756 KB Output is correct
9 Correct 219 ms 61300 KB Output is correct
10 Correct 165 ms 59920 KB Output is correct
11 Correct 221 ms 60808 KB Output is correct
12 Correct 8 ms 45656 KB Output is correct
13 Correct 1722 ms 206448 KB Output is correct
14 Correct 2558 ms 289308 KB Output is correct
15 Correct 655 ms 121180 KB Output is correct
16 Correct 3372 ms 372476 KB Output is correct
17 Correct 2624 ms 307580 KB Output is correct
18 Correct 737 ms 96100 KB Output is correct
19 Correct 324 ms 74052 KB Output is correct
20 Correct 835 ms 111272 KB Output is correct
21 Correct 756 ms 96904 KB Output is correct
22 Correct 1893 ms 232096 KB Output is correct
23 Correct 2039 ms 237588 KB Output is correct
24 Correct 3034 ms 319340 KB Output is correct
25 Correct 2940 ms 321148 KB Output is correct
26 Correct 2917 ms 313288 KB Output is correct
27 Correct 3699 ms 384656 KB Output is correct
28 Correct 744 ms 128608 KB Output is correct
29 Correct 2850 ms 312656 KB Output is correct
30 Correct 2903 ms 312708 KB Output is correct
31 Correct 2864 ms 312656 KB Output is correct
32 Correct 874 ms 117016 KB Output is correct
33 Correct 268 ms 74540 KB Output is correct
34 Correct 490 ms 91220 KB Output is correct
35 Correct 507 ms 91660 KB Output is correct
36 Correct 649 ms 95640 KB Output is correct
37 Correct 648 ms 95408 KB Output is correct