Submission #552211

#	Time	Username	Problem	Language	Result	Execution time	Memory
552211		cadmiumsky	Factories (JOI14_factories)	C++14	0 / 100	2515 ms	524288 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)
// defapt, nu se poate mai bine de centroid???
// asta e doar o fita confirmed???

const int nmax = 5e5 + 5;

vector< pair<int,int> > g[nmax];

namespace LCA {
  int father[nmax][19], pin[nmax], pout[nmax], inp, depth[nmax], h[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 < 19; i++)
      father[node][i] = father[father[node][i]][i];
    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 = 18; i >= 0; i--) 
      if(!isanc(father[x][i], y))
        x = father[x][i];
    return father[x][0];
  }
  int dist(int x, int y) {
    return depth[x] + depth[y] - 2 * depth[lca(x, y)];
  }  
}
struct PartTree {
  vector< pair<int,int> > t[nmax];
  vector<int> nds;
  int color[nmax], dist[nmax];
  void addedge(int x, int y, int c) { nds.push_back(x), t[x].push_back({y, c}), 
                                      nds.push_back(y), t[y].push_back({x, c}); };
  void clear(int x) { dist[x] = 0, color[x] = 0, t[x].clear(); }
  priority_queue< pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > heap;
  #warning VERIFICA SA NU BUSESTI DIJKSTRA-UL SI ACUM PUII MEI
  int dijkstra() {
    if(heap.empty())
      return -1;
    int node, cost;
    tie(cost, node) = heap.top();
    heap.pop();
    if(cost > dist[node]) {
      return dijkstra();
    }
    if(color[node] == 2)
      return cost;
    for(auto [x, c] : t[node]) {
      if(dist[x] > dist[node] + c) {
        dist[x] = dist[node] + c;
        heap.push({dist[x], x});
      }
    }
    return dijkstra();
  }
  int answer(vector<int> l, vector<int> 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, LCA::dist(lastadded, st.back()));
      }
      if(lastadded != high)
        addedge(high, lastadded, LCA::dist(lastadded, high));
      st.push_back(high);
      if(high != node)
        st.push_back(node);
    }
    int temp;
    while(st.size() > 1) {
      temp = st.back(), st.pop_back();
      addedge(st.back(), temp, LCA::dist(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<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >();
    for(auto x : nds)
      clear(x);
    nds.clear();
    return temp;
  }
} ttrick;

#undef int
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<long long> 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]);
  return ttrick.answer(l, r);
}

Compilation message (stderr)

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

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