oj.uz

Submission #700997

# Submission time Handle Problem Language Result Execution time Memory
700997 2023-02-19T16:39:01 Z angelo_torres Factories (JOI14_factories) C++17
0 / 100
 685 ms 524288 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define ff first
#define ss second

using namespace std;
typedef long long ll;
const ll N = 5e5 + 10;
const ll M = 2e6 + 20;
const ll inf = 1e17;

int n,t[N],p[N];
ll d[N],q[N];
vector<pair<int,ll>> g[N];
deque<ll> s[N];

void dfs(int v,int f){
  t[v] = 1;
  for(auto [u,w] : g[v]){
    if(u == f) continue;
    dfs(u,v);
    t[v] += t[u];
  }
}

int find(int v,int f,int tm){
  for(auto [u,w] : g[v]){
    if(u == f) continue;
    if(t[u]*2 > tm) return find(u,v,tm);
  }
  return v;
}

void gfs(int v,int f){
  s[v].push_front(d[v]);
  for(auto [u,w] : g[v]){
    if(u == f) continue;
    d[u] = d[v] + w;
    gfs(u,v);
  }
}

void build(int v,int f){
  dfs(v,f);
  // for(int i = 0; i < n; ++i) printf("%d ", t[i]);
  // printf("\n");
  int c = find(v,f,t[v]);
  // printf("%d \n",c);
  d[v] = 0, p[c] = f;
  gfs(c,f);
  for(auto [u,w] : g[c]){
    if(u == f) continue;
    build(u,c);
  }
}

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],(ll) D[i]});
    g[B[i]].push_back({A[i],(ll) D[i]});
  }
  for(int i = 0; i < n; ++i) q[i] = inf;
  build(0,-1);
  // for(int i = 0; i < n; ++i){
  //   for(auto it : s[i]) printf("%lld ",it);
  //   printf("\n");
  // }
}

long long Query(int S, int X[], int T, int Y[]){
  for(int i = 0; i < S; ++i){
    int aux = X[i], id = 0;
    while(aux != -1){
      q[aux] = min(q[aux],s[X[i]][id]);
      aux = p[aux], id++;
    }
  }
  ll ans = inf;
  for(int i = 0; i < T; ++i){
    int aux = Y[i], id = 0;
    while(aux != -1){
      ans = min(ans,q[aux]+s[Y[i]][id]);
      aux = p[aux], id++;
    }
  }
  for(int i = 0; i < S; ++i){
    int aux = X[i];
    while(aux != -1) q[aux] = inf, aux = p[aux];
  }
  return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 652 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 685 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 652 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -