Submission #319717

#	Time	Username	Problem	Language	Result	Execution time	Memory
319717		tushar_2658	Factories (JOI14_factories)	C++14	100 / 100	4191 ms	198360 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 500005;
using ll = long long;
const ll inf = 1e18;

vector<pair<int, ll>> edges[maxn];
int n;
int sub[maxn], par[maxn], cent_dep[maxn];
int cent_vis[maxn];
ll mn[maxn], cent_dis[maxn][20];
stack<int> st;

void dfs(int x, int p, int d){
  sub[x] = 1;
  for(auto i : edges[x]){
    if(i.first != p){
      if(!cent_vis[i.first]){
        if(d){
          cent_dis[i.first][d - 1] = cent_dis[x][d - 1] + i.second;
        }
        dfs(i.first, x, d);
        sub[x] += sub[i.first];
      }
    }
  }
}

int find_centroid(int x, int p, int range){
  for(auto i : edges[x]){
    if(i.first != p && !cent_vis[i.first]){
      if(sub[i.first] > range)return find_centroid(i.first, x, range);
    }
  }return x;
}

void build(int x, int p, int d){
  dfs(x, -1, d);
  int c = find_centroid(x, -1, sub[x] / 2);
  par[c] = p;
  cent_vis[c] = 1;
  cent_dep[c] = d;
  for(auto i : edges[c]){
    if(!cent_vis[i.first]){
      cent_dis[i.first][d] = i.second;
      build(i.first, c, d + 1);
    }
  }
  cent_vis[c] = 0;
}

void upd(int x){
  int cur = x;
  while(cur != 0){
    mn[cur] = min(mn[cur], cent_dis[x][cent_dep[cur]]);
    st.push(cur);
    cur = par[cur];
  }
}

ll query(int x){
  ll ret = mn[x];
  int cur = x;
  while(cur != 0){
    ret = min(ret, mn[cur] + cent_dis[x][cent_dep[cur]]);
    cur = par[cur];
  }
  return ret;
}

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

long long Query(int S, int X[], int T, int Y[]) {
  for(int i = 0; i < S; ++i){
    upd(X[i] + 1);
  }
  ll ans = inf;
  for(int i = 0; i < T; ++i){
    ans = min(ans, query(Y[i] + 1));
  }
  while(!st.empty()){
    mn[st.top()] = inf;
    st.pop();
  }
  return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67