Submission #520387

#	Time	Username	Problem	Language	Result	Execution time	Memory
520387		Alex_tz307	Arboras (RMI20_arboras)	C++17	100 / 100	128 ms	23108 KiB

arboras

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
const int mod = 1e9 + 7;
vector<int> g[1 + kN];
int depth[1 + kN], bestSon[1 + kN], ans;
int64_t max1[1 + kN], max2[1 + kN];

struct edge {
  int par;
  int64_t len;
} edges[1 + kN];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct treapNode {
  treapNode* l;
  treapNode* r;
  treapNode* par;
  int node, prior, sz;
  int64_t maxChain, lazy;
};

using ptr = treapNode*;
using pt = pair<ptr, ptr>;

ptr emptyNode = new treapNode{nullptr, nullptr, nullptr, 0, -1, 0, 0, 0};
ptr roots[1 + kN];

inline void updateNode(ptr node) {
  if (node != emptyNode) {
    node->sz = 1 + node->l->sz + node->r->sz;
    node->par = nullptr;
    if (node->l != emptyNode) {
      node->l->par = node;
    }
    if (node->r != emptyNode) {
      node->r->par = node;
    }
  }
}

inline void incNode(ptr node, const int64_t &val) {
  node->maxChain += val;
  node->lazy += val;
}

inline void push(ptr node) {
  if (node != emptyNode && node->lazy != 0) {
    if (node->l != emptyNode) {
      incNode(node->l, node->lazy);
    }
    if (node->r != emptyNode) {
      incNode(node->r, node->lazy);
    }
    node->lazy = 0;
  }
}

pt split(ptr node, const int &k) {
  if (node == emptyNode) {
    return {emptyNode, emptyNode};
  }
  push(node);
  if (node->l->sz < k) {
    pt p = split(node->r, k - node->l->sz - 1);
    node->r = p.first;
    updateNode(node);
    return {node, p.second};
  }
  pt p = split(node->l, k);
  node->l = p.second;
  updateNode(node);
  return {p.first, node};
}

ptr join(ptr A, ptr B) {
  if (A == emptyNode) {
    return B;
  }
  if (B == emptyNode) {
    return A;
  }
  push(A);
  push(B);
  if (B->prior < A->prior) {
    A->r = join(A->r, B);
    updateNode(A);
    return A;
  }
  B->l = join(A, B->l);
  updateNode(B);
  return B;
}

int getNode(ptr node, const int &k) {
  if (node == emptyNode) {
    return 0;
  }
  if (node->l->sz == k - 1) {
    return node->node;
  }
  push(node);
  if (k <= node->l->sz) {
    return getNode(node->l, k);
  }
  return getNode(node->r, k - node->l->sz - 1);
}

inline int findRoot(ptr node) {
  ptr root = node;
  while (root->par) {
    root = root->par;
  }
  return root->node;
}

inline int findChainTop(ptr node) {
  ptr root = roots[findRoot(node)];
  while (root->l != emptyNode) {
    root = root->l;
  }
  return root->node;
}

inline void maxSelf(int64_t &x, const int64_t &y) {
  if (x < y) {
    x = y;
  }
}

inline int norm(int64_t x) {
  if (x >= mod) {
    x %= mod;
  }
  return x;
}

inline void addSelf(int &x, const int &y) {
  x += y;
  if (x < 0) {
    x += mod;
  }
  if (x >= mod) {
    x -= mod;
  }
}

inline int mult(const int64_t &x, const int &y) {
  return norm(x * y);
}

void dfs1(const int &u) {
  for (const int &v : g[u]) {
    depth[v] = depth[u] + 1;
    dfs1(v);
    int64_t chainLen = max1[v] + edges[v].len;
    if (max1[u] < chainLen) {
      max2[u] = max1[u];
      max1[u] = chainLen;
      bestSon[u] = v;
    } else {
      maxSelf(max2[u], chainLen);
    }
  }
}

void dfs2(const int &u, ptr node) {
  addSelf(ans, norm(max1[u]));
  addSelf(ans, norm(max2[u]));
  if (bestSon[u] == 0) {
    return;
  }
  node = join(node, roots[bestSon[u]]);
  dfs2(bestSon[u], node);
  for (int v : g[u]) {
    if (v != bestSon[u]) {
      dfs2(v, roots[v]);
    }
  }
}

void updateChainPreff(const int &node, const int64_t &k) {
  int tRoot = findRoot(roots[node]);
  int chainTop = findChainTop(roots[node]);
  int preff = depth[node] - depth[chainTop] + 1;
  addSelf(ans, mult(k, preff));
  ptr upChain, downChain;
  tie(upChain, downChain) = split(roots[tRoot], preff);
  incNode(upChain, k);
  join(upChain, downChain);
  if (chainTop == 1) {
    return;
  }
  int par = edges[chainTop].par;
  int ptRoot = findRoot(roots[par]);
  int pChainTop = findChainTop(roots[par]);
  int preffPar = depth[par] - depth[pChainTop] + 1;
  int son = getNode(roots[ptRoot], preffPar + 1);
  getNode(roots[tRoot], 1);
  int64_t inc = roots[chainTop]->maxChain + edges[chainTop].len - (roots[son]->maxChain + edges[son].len);
  if (inc <= 0) {
    addSelf(ans, -norm(max2[par]));
    maxSelf(max2[par], roots[chainTop]->maxChain + edges[chainTop].len);
    addSelf(ans, norm(max2[par]));
  } else {
    ptr upChain, downChain;
    tie(upChain, downChain) = split(roots[ptRoot], preffPar);
    join(upChain, roots[tRoot]);
    addSelf(ans, -norm(max2[par]));
    maxSelf(max2[par], roots[son]->maxChain + edges[son].len);
    addSelf(ans, norm(max2[par]));
    updateChainPreff(par, inc);
  }
}

void testCase() {
  int n;
  cin >> n;
  for (int v = 2; v <= n; ++v) {
    int u;
    cin >> u;
    ++u;
    edges[v].par = u;
    g[u].emplace_back(v);
  }
  for (int v = 2; v <= n; ++v) {
    int d;
    cin >> d;
    edges[v].len = d;
  }
  dfs1(1);
  for (int v = 1; v <= n; ++v) {
    roots[v] = new treapNode{emptyNode, emptyNode, nullptr, v, rng() % mod, 1, max1[v], 0};
  }
  dfs2(1, roots[1]);
  cout << ans << '\n';
  int q;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int v, k;
    cin >> v >> k;
    ++v;
    edges[v].len += k;
    if (v == findChainTop(roots[v])) {
      int tRoot = findRoot(roots[v]);
      int par = edges[v].par;
      int ptRoot = findRoot(roots[par]);
      int pChainTop = findChainTop(roots[par]);
      int preff = depth[par] - depth[pChainTop] + 1;
      int son = getNode(roots[ptRoot], preff + 1);
      getNode(roots[tRoot], 1);
      int64_t inc = roots[v]->maxChain + edges[v].len - (roots[son]->maxChain + edges[son].len);
      if (inc <= 0) {
        addSelf(ans, -norm(max2[par]));
        maxSelf(max2[par], roots[v]->maxChain + edges[v].len);
        addSelf(ans, norm(max2[par]));
      } else {
        ptr upChain, downChain;
        tie(upChain, downChain) = split(roots[ptRoot], preff);
        join(upChain, roots[tRoot]);
        addSelf(ans, -norm(max2[par]));
        maxSelf(max2[par], roots[son]->maxChain + edges[son].len);
        addSelf(ans, norm(max2[par]));
        updateChainPreff(par, inc);
      }
    } else {
      updateChainPreff(edges[v].par, k);
    }
    cout << ans << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    testCase();
  }
  return 0;
}

Compilation message (stderr)

arboras.cpp: In function 'void testCase()':
arboras.cpp:236:70: warning: narrowing conversion of '(rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()() % ((std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)((int)mod)))' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  236 |     roots[v] = new treapNode{emptyNode, emptyNode, nullptr, v, rng() % mod, 1, max1[v], 0};
      |                                                                ~~~~~~^~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45