Submission #1257731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257731		jahongir	Factories (JOI14_factories)	C++20	100 / 100	1643 ms	120644 KiB

factories

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

#define ll long long
#define pi pair<int,int>
#define pb push_back
#define all(a)  begin(a), end(a)

const ll inf = 1e18;
const int mxn = 5e5+10, lg2 = 19;
vector<pi> g[mxn];
int suc[mxn][lg2];
int tin[mxn], tout[mxn], tim = 0;
ll dep[mxn], dp[mxn][2];


void dfs(int u, int p, ll dis){
  suc[u][0] = p, dep[u] = dis;
  for(int i = 1; i < lg2; i++)
    suc[u][i] = suc[suc[u][i-1]][i-1];
  
  tin[u] = tim++;

  for(auto [v,c] : g[u]) if(v!=p)
    dfs(v,u,dis+c);

  tout[u] = tim++; g[u].clear();
}

bool is_anc(int u, int v){
  return tin[u]<=tin[v] && tout[v]<=tout[u];
}

int get_lca(int u, int v){
  if(is_anc(u,v)) return u;
  if(is_anc(v,u)) return v;
  for(int i = lg2-1; i>=0; i--)
    if(!is_anc(suc[u][i],v))
      u = suc[u][i];
  return suc[u][0];
}

bool cmp(int u, int v){
  return tin[u] < tin[v];
}


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

long long Query(int S, int X[], int T, int Y[]) {
  vector<int> vec;

  for(int i = 0; i < S; i++){
    dp[X[i]][0] = dep[X[i]]; vec.pb(X[i]);
  }

  for(int i = 0; i < T; i++){
    dp[Y[i]][1] = dep[Y[i]]; vec.pb(Y[i]);
  }

  sort(all(vec),cmp);

  for(int i = 0; i < S+T-1; i++)
    vec.pb(get_lca(vec[i],vec[i+1]));

  sort(all(vec),cmp); vec.erase(unique(all(vec)),vec.end());


  stack<int> st;
  for(auto u : vec){
    while(!st.empty() && !is_anc(st.top(),u)) st.pop();
    if(!st.empty()) g[st.top()].pb({u,0});
    st.push(u);
  }

  reverse(all(vec));

  ll ans = inf;

  for(auto u : vec){
    for(auto [v,c] : g[u]){
      dp[u][0] = min(dp[u][0],dp[v][0]);
      dp[u][1] = min(dp[u][1],dp[v][1]);
    }
    ans = min(ans,dp[u][0] + dp[u][1] - 2*dep[u]);
  }

  for(auto u : vec){
    g[u].clear(); dp[u][0] = dp[u][1] = inf;
  }

  return ans;
}

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