Submission #700997

#	Time	Username	Problem	Language	Result	Execution time	Memory
700997		angelo_torres	Factories (JOI14_factories)	C++17	0 / 100	685 ms	524288 KiB

factories

#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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67