oj.uz

답안 #520387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520387 2022-01-29T18:27:47 Z Alex_tz307 Arboras (RMI20_arboras) C++17
100 / 100
 128 ms 23108 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 2 ms 2764 KB Output is correct
2 Correct 3 ms 2892 KB Output is correct
3 Correct 2 ms 2824 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 18152 KB Output is correct
2 Correct 55 ms 14688 KB Output is correct
3 Correct 62 ms 14892 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 20332 KB Output is correct
2 Correct 112 ms 21568 KB Output is correct
3 Correct 114 ms 16536 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 3 ms 2892 KB Output is correct
3 Correct 2 ms 2824 KB Output is correct
4 Correct 128 ms 18152 KB Output is correct
5 Correct 55 ms 14688 KB Output is correct
6 Correct 62 ms 14892 KB Output is correct
7 Correct 128 ms 20332 KB Output is correct
8 Correct 112 ms 21568 KB Output is correct
9 Correct 114 ms 16536 KB Output is correct
10 Correct 128 ms 20136 KB Output is correct
11 Correct 106 ms 21316 KB Output is correct
12 Correct 92 ms 16392 KB Output is correct
13 Correct 93 ms 22468 KB Output is correct
14 Correct 103 ms 23108 KB Output is correct