Submission #552571

#	Time	Username	Problem	Language	Result	Execution time	Memory
552571		cadmiumsky	Factories (JOI14_factories)	C++14	0 / 100	1792 ms	131920 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
//#define int long long
// Solutie: LCA Tree + Dijkstra

using namespace std; // asta e pentru &u' (ca poate bagam centroid decomp idk)
using ll = long long;
// defapt, nu se poate mai bine de centroid???
// asta e doar o fita confirmed???

const int nmax = 5e5 + 5;

vector< pair<int,ll> > g[nmax];
//#define int ll
namespace LCA {
  int father[nmax][21], pin[nmax], pout[nmax], inp, h[nmax];
  ll depth[nmax];
  auto bypin = [](int a, int b) { return pin[a] < pin[b];};
  void init(int node = 0, int f = 0) {
    pin[node] = inp++;
    father[node][0] = f;
    h[node] = h[f] + 1;
    for(int i = 1; i < 21; i++)
      father[node][i] = father[father[node][i - 1]][i - 1];
    for(auto [x, c] : g[node]) {
      if(x != f)
        depth[x] = depth[node] + c, init(x, node);
    }
    pout[node] = inp - 1;
  }
  bool isanc(int f, int node) { return pin[f] <= pin[node] && pout[node] <= pout[f]; }
  int lca(int x, int y) {
    if(isanc(x,  y))
      return x;
    if(isanc(y, x))
      return y;
    for(int i = 20; i >= 0; i--) 
      if(!isanc(father[x][i], y))
        x = father[x][i];
    return father[x][0];
  }
  ll dist(int x, int y) {
    int l = lca(x, y);
    return depth[x] + depth[y] - 2 * depth[l];
  }  
}
//#undef int
struct PartTree {
  vector< int > t[nmax];
  vector<int> nds;
  char color[nmax];
  ll dist[nmax];
  void addedge(int x, int y) {nds.push_back(x), t[x].push_back(y), 
                                      nds.push_back(y), t[y].push_back(x); };
  void clear(int x) { dist[x] = 0, color[x] = 0, t[x].clear(); }
  priority_queue< pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > heap;
  #warning VERIFICA SA NU BUSESTI DIJKSTRA-UL SI ACUM PUII MEI
  ll dijkstra() {
    if(heap.empty())
      assert(false);
    int node, cost;
    tie(cost, node) = heap.top();
    heap.pop();
    if(cost > dist[node]) {
      return dijkstra();
    }
    if(color[node] == 2)
      return cost;
    #define int ll
    for(auto x : t[node]) {
      ll c = max(LCA::dist(x, node), LCA::dist(node, x));
      if(dist[x] > dist[node] + c) {
        dist[x] = dist[node] + c;
        assert(dist[node] + c > 0);
        heap.push({dist[x], x});
      }
    }
    #undef int
    return dijkstra();
  }
  ll answer(vector<signed> l, vector<signed> r) {
    vector<int>list;
    for(auto x : l)
      color[x] = 1, list.push_back(x);
    for(auto y : r)
      color[y] = 2, list.push_back(y);
    sort(list.begin(), list.end(), LCA::bypin);
    vector<int> st;
    for(auto node : list) {
      if(st.empty()) {
        st.push_back(node);
        continue;
      }
      int high = LCA::lca(node, st.back());
      int lastadded = high;
      while(!st.empty() && LCA::h[st.back()] >= LCA::h[high]) {
        lastadded = st.back();
        st.pop_back();
        if(!st.empty() && !(LCA::h[st.back()] < LCA::h[high]))
          addedge(st.back(), lastadded);
      }
      if(lastadded != high)
        addedge(high, lastadded);
      st.push_back(high);
      if(high != node)
        st.push_back(node);
    }
    ll temp;
    while(st.size() > 1) {
      temp = st.back(), st.pop_back();
      addedge(st.back(), temp);
    }
    sort(nds.begin(), nds.end());
    nds.resize(distance(nds.begin(), unique(nds.begin(), nds.end())));
    for(auto x : nds)
      if(color[x] == 1)
        heap.push({0, x});
      else
        dist[x] = 5e13L + 5LL;
    
    temp = dijkstra();
    heap = priority_queue< pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > >();
    for(auto x : nds)
      clear(x);
    nds.clear();
    return temp;
  }
  //#undef int
} ttrick;

void Init(int N, int A[], int B[], int D[]) {
  for(int i = 0; i < N - 1; i++)
    g[A[i]].push_back({B[i], D[i]}),
    g[B[i]].push_back({A[i], D[i]});
  LCA::init();
}

long long Query(int S, int X[], int T, int Y[]) {
  vector<int> l, r;
  for(int i = 0; i < S; i++)
    l.push_back(X[i]);
  for(int i = 0; i < T; i++)
    r.push_back(Y[i]);
  ll o = ttrick.answer(l, r);
  return o;
}

Compilation message (stderr)

factories.cpp:57:4: warning: #warning VERIFICA SA NU BUSESTI DIJKSTRA-UL SI ACUM PUII MEI [-Wcpp]
   57 |   #warning VERIFICA SA NU BUSESTI DIJKSTRA-UL SI ACUM PUII MEI
      |    ^~~~~~~
factories.cpp: In function 'void LCA::init(int, int)':
factories.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto [x, c] : g[node]) {
      |              ^

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