Submission #319714

#	Time	Username	Problem	Language	Result	Execution time	Memory
319714		tushar_2658	Factories (JOI14_factories)	C++14	15 / 100	8031 ms	257840 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;
ll dis[maxn], sparse[maxn][20];
int depth[maxn];

void dfs(int x, int p, ll c){
  dis[x] = c;
  depth[x] = depth[p] + 1;
  sparse[x][0] = p;
  for(auto i : edges[x]){
    if(i.first != p){
      dfs(i.first, x, c + i.second);
    }
  }
} 

void build_lca(){
  for(int j = 1; j < 20; ++j){
    for(int i = 1; i <= n; ++i){
      if(sparse[i][j - 1] != 0){
        sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
      }
    }
  }
}

int LCA(int x, int y){
  if(depth[x] < depth[y])swap(x, y);
  for(int i = 19; i >= 0; --i){
    if(depth[x] - (1 << i) >= depth[y]){
      x = sparse[x][i];
    }
  }
  if(x == y)return x;
  for(int i = 19; i >= 0; --i){
    if(sparse[x][i] != sparse[y][i] && sparse[x][i] != 0 && sparse[y][i] != 0){
      x = sparse[x][i];
      y = sparse[y][i];
    }
  }
  return sparse[x][0];
}

ll DIS(int x, int y){
  return dis[x] + dis[y] - (2 * dis[LCA(x, y)]);
}

int sub[maxn], par[maxn], cent_dep[maxn];
int cent_vis[maxn];

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

ll mn[maxn], cent_dis[maxn][20];

void calc(int x){
  int cur = x, lvl = 0;
  while(cur != 0){
    cent_dis[x][lvl] = DIS(cur, x);
    cur = par[cur];
    ++lvl;
  }
}

stack<int> st;

void upd(int x){
  int cur = x;
  while(cur != 0){
    mn[cur] = min(mn[cur], cent_dis[x][cent_dep[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[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]});
  }
  dfs(1, 1, 0);
  build_lca();
  build(1, 0, 1);
  for(int i = 1; i <= N; ++i){
    calc(i);
  }
  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: 0 / 18
• Subtask 3: 0 / 67