oj.uz

Submission #993806

# Submission time Handle Problem Language Result Execution time Memory
993806 2024-06-06T12:45:22 Z UVince Factories (JOI14_factories) C++17
0 / 100
 26 ms 62040 KB 
#include <bits/stdc++.h>
#include "factories.h"
using ll=long long;
using namespace std;

const int maxn = 5e5+1;
vector<vector<pair<int,ll>>> g(maxn);
vector<int> parent(maxn);
vector<int> subsize(maxn);
vector<bool> isremoved(maxn,false);
vector<map<int, ll>> d(maxn);
vector<ll> far(maxn, INT_MAX);
vector<int> valid(maxn, 0);


int getsize(int v, int par=-1){
  subsize[v]=1;
  for (auto [to, dist] : g[v]){
    if (to == par || isremoved[to]) continue;
    subsize[v]+=getsize(to, v);
  }
  return subsize[v];
}

int getc(int v, int ts, int par=-1){
  for (auto [to, dist] : g[v]){
    if (to==par || isremoved[to]) continue;
    if (subsize[to]*2>ts) return getc(to,ts,v);
  }
  return v;
}

void calcdist(int v, int c, int par=-1){
  for (auto [to, dist] : g[v]){
    if (to==par || isremoved[to]) continue;
    d[c][to]=d[c][v]+dist;
    calcdist(to,c,v);
  }
}

void build(int v, int par){

  int c = getc(v, getsize(v));
  parent[c]=par;

  isremoved[c]=true;
  for (auto [to, dist] : g[c]){
    if (isremoved[to]) continue;
    d[c][to]=dist;
    calcdist(to, c, c);
    build(to, c);
  }
}

void Init(int N, int A[], int B[], int D[]) {
  for (int i=0;i<N-1;i++){
    g[A[i]+1].push_back({B[i]+1,D[i]});
    g[B[i]+1].push_back({A[i]+1, D[i]});
  }
  build(1, -1);

}

int id=0;

long long Query(int S, int X[], int T, int Y[]) {
  //y->x
  id++;
  for (int i=0;i<S;i++){
    int cur = X[i]+1;
    far[cur]=0;
    valid[cur]=id;
    auto p = parent[cur];
    while (p!=-1){
      if (valid[p]==id){
        if (far[cur]+d[p][cur]<far[p]){
          far[p]=far[cur]+d[p][cur];
        }
      }
      else {
        far[p]=far[cur]+d[p][cur];
        valid[p]=id;
      }
      p=parent[p];
    }
  }
  ll ans=1e11;
  for (int i=0;i<T;i++){
    int cur = Y[i]+1;
    auto p = parent[cur];
    while (p!=-1){
      if (valid[p]==id) ans=min(ans, far[p]+d[p][cur]);
      p=parent[p];
    }
  }
  return ans;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

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