oj.uz

Submission #854443

# Submission time Handle Problem Language Result Execution time Memory
854443 2023-09-27T16:36:30 Z gun_gan Factories (JOI14_factories) C++17
0 / 100
 15 ms 45912 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, int 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]});
      }

      build(1);
      for(int i = 1; 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 45912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 45812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 45912 KB Output isn't correct
2 Halted 0 ms 0 KB -