oj.uz

Submission #552576

# Submission time Handle Problem Language Result Execution time Memory
552576 2022-04-23T10:27:57 Z cadmiumsky Factories (JOI14_factories) C++14
100 / 100
 4793 ms 176376 KB 
#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; 
    ll 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 = 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

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24276 KB Output is correct
2 Correct 1036 ms 33432 KB Output is correct
3 Correct 1152 ms 33200 KB Output is correct
4 Correct 1033 ms 33528 KB Output is correct
5 Correct 743 ms 40416 KB Output is correct
6 Correct 920 ms 40252 KB Output is correct
7 Correct 1163 ms 40008 KB Output is correct
8 Correct 1064 ms 40308 KB Output is correct
9 Correct 726 ms 40304 KB Output is correct
10 Correct 894 ms 40060 KB Output is correct
11 Correct 1112 ms 40080 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24020 KB Output is correct
2 Correct 1943 ms 131624 KB Output is correct
3 Correct 2794 ms 150848 KB Output is correct
4 Correct 1464 ms 147468 KB Output is correct
5 Correct 1667 ms 176376 KB Output is correct
6 Correct 2996 ms 153260 KB Output is correct
7 Correct 2473 ms 67876 KB Output is correct
8 Correct 1414 ms 68116 KB Output is correct
9 Correct 1141 ms 72048 KB Output is correct
10 Correct 2511 ms 69336 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24276 KB Output is correct
2 Correct 1036 ms 33432 KB Output is correct
3 Correct 1152 ms 33200 KB Output is correct
4 Correct 1033 ms 33528 KB Output is correct
5 Correct 743 ms 40416 KB Output is correct
6 Correct 920 ms 40252 KB Output is correct
7 Correct 1163 ms 40008 KB Output is correct
8 Correct 1064 ms 40308 KB Output is correct
9 Correct 726 ms 40304 KB Output is correct
10 Correct 894 ms 40060 KB Output is correct
11 Correct 1112 ms 40080 KB Output is correct
12 Correct 15 ms 24020 KB Output is correct
13 Correct 1943 ms 131624 KB Output is correct
14 Correct 2794 ms 150848 KB Output is correct
15 Correct 1464 ms 147468 KB Output is correct
16 Correct 1667 ms 176376 KB Output is correct
17 Correct 2996 ms 153260 KB Output is correct
18 Correct 2473 ms 67876 KB Output is correct
19 Correct 1414 ms 68116 KB Output is correct
20 Correct 1141 ms 72048 KB Output is correct
21 Correct 2511 ms 69336 KB Output is correct
22 Correct 3139 ms 143276 KB Output is correct
23 Correct 3170 ms 143076 KB Output is correct
24 Correct 3606 ms 145892 KB Output is correct
25 Correct 3830 ms 147032 KB Output is correct
26 Correct 4685 ms 141820 KB Output is correct
27 Correct 2413 ms 163400 KB Output is correct
28 Correct 2264 ms 142208 KB Output is correct
29 Correct 4698 ms 140132 KB Output is correct
30 Correct 4769 ms 139820 KB Output is correct
31 Correct 4793 ms 141432 KB Output is correct
32 Correct 1282 ms 76496 KB Output is correct
33 Correct 1510 ms 72752 KB Output is correct
34 Correct 2106 ms 66028 KB Output is correct
35 Correct 2059 ms 66040 KB Output is correct
36 Correct 2354 ms 66372 KB Output is correct
37 Correct 2354 ms 66532 KB Output is correct