oj.uz

답안 #520392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520392 2022-01-29T18:32:43 Z Alex_tz307 Arboras (RMI20_arboras) C++17
100 / 100
 140 ms 22084 KB 
#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

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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 3 ms 2812 KB Output is correct
3 Correct 2 ms 2820 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 16556 KB Output is correct
2 Correct 72 ms 13364 KB Output is correct
3 Correct 58 ms 13616 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 17956 KB Output is correct
2 Correct 115 ms 19720 KB Output is correct
3 Correct 87 ms 14796 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 3 ms 2812 KB Output is correct
3 Correct 2 ms 2820 KB Output is correct
4 Correct 127 ms 16556 KB Output is correct
5 Correct 72 ms 13364 KB Output is correct
6 Correct 58 ms 13616 KB Output is correct
7 Correct 119 ms 17956 KB Output is correct
8 Correct 115 ms 19720 KB Output is correct
9 Correct 87 ms 14796 KB Output is correct
10 Correct 140 ms 18464 KB Output is correct
11 Correct 105 ms 19740 KB Output is correct
12 Correct 89 ms 14824 KB Output is correct
13 Correct 99 ms 21340 KB Output is correct
14 Correct 107 ms 22084 KB Output is correct