Submission #656635

#	Time	Username	Problem	Language	Result	Execution time	Memory
656635		uylulu	Factories (JOI14_factories)	C++17	100 / 100	4794 ms	301760 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>

#define ll long long


using namespace std;

const ll N = 5e5 + 5,K = 23,oo = 1e17;

vector<pair<ll,ll>> adj[N + 1];
ll dis[N + 1],fi[N + 1],t = 0;

ll eu[2*N + 1],sparse[2*N + 1][K + 1];


void dfs(ll s,ll pa) {
  fi[s] = t;
  eu[t] = s;
  t++;
  for(auto u : adj[s]) {
    if(u.first == pa) continue;

    dis[u.first] = dis[s] + u.second;
    dfs(u.first,s);

    eu[t] = s;
    t++;
  }
}

ll lg[2*N + 1];

void build() {
  for(ll i = 2;i <= t;i++) {
    lg[i] = lg[i/2] + 1;
  }

  for(ll i = 0;i < t;i++) {
    sparse[i][0] = dis[eu[i]];
  } 
  for(ll j = 1;j <= K;j++) {
    for(ll i = 0;i + (1<<j) <= t;i++) {
      sparse[i][j] = min(sparse[i][j - 1],sparse[i + (1<<(j - 1))][j - 1]);
    }
  }
}

ll query(ll l,ll r) {
  if(l > r) swap(l,r);

  ll len = lg[r - l + 1];
  return min(sparse[l][len],sparse[r - (1<<len) + 1][len]);
}

ll lca(ll a,ll b) {
  return query(fi[a],fi[b]);
}

ll help_dis(ll a,ll b) {
  return dis[a] + dis[b] - 2*lca(a,b);
}

ll cha[N + 1],sz[N + 1];
bool dele[N + 1];

void init(ll s,ll pa) {
  sz[s] = 1;
  for(auto u : adj[s]) {
    if(u.first == pa || dele[u.first]) continue;

    init(u.first,s);

    sz[s] += sz[u.first];
  }
}

ll find_cen(ll s,ll cnt,ll pa) {
  for(auto u : adj[s]) {
    if(dele[u.first] || u.first == pa) continue;

    if(sz[u.first]*2 > cnt) {
      return find_cen(u.first,cnt,s);
    }
  }
  return s;
}

void decompose(ll s,ll pa) {
  init(s,-1);
  ll u = find_cen(s,sz[s],pa);
  dele[u] = true;

  cha[u] = pa;

  for(auto v : adj[u]) {
    if(dele[v.first]) continue;
    decompose(v.first,u);
  }
}

ll dp[N + 1];

void Init(int len, int A[], int B[], int D[]) {
  int n = len;
  for(int i = 0;i < n - 1;i++) {
    adj[A[i]].push_back({B[i],D[i]});
    adj[B[i]].push_back({A[i],D[i]});
  }

  for(int i = 0;i < n;i++) {
    fi[i] = oo;
    dp[i] = oo;
  }
  dfs(0,-1);
  build();
  decompose(0,-1);
  
}


long long Query(int s, int x[], int t, int y[]) {


  for(ll i = 0;i < s;i++) {
    ll crr = x[i];

    while(crr != -1) {
      dp[crr] = min(dp[crr],help_dis(crr,x[i]));
      crr = cha[crr];
    }
    // cout<<endl;
  }

  ll res = oo;

  for(int i = 0;i < t;i++) {
    int crr = y[i];

    while(crr != -1) {
      res = min(res,dp[crr] + help_dis(crr,y[i]));
      crr = cha[crr];
      // cout<<crr<<" "<<dp[crr]<<" ";
    }
    // cout<<endl;
  }

  for(ll i = 0;i < s;i++) {
    ll crr = x[i];

    while(crr != -1) {
      dp[crr] = oo;
      crr = cha[crr];
    }
  }

  return res;
}

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