#386666 (C++17) No.900 aδδitivee

提出ソース

結果

問題	No.900 aδδitivee
ユーザー	👑 emthrm
提出日時	2019-10-04 21:54:23
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	100 ms / 2,000 ms
コード長	6,603 bytes
コンパイル時間	2,097 ms
コンパイル使用メモリ	138,620 KB
実行使用メモリ	21,060 KB
最終ジャッジ日時	2024-10-03 07:33:42
合計ジャッジ時間	5,424 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	1 ms 6,816 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	95 ms 17,284 KB
testcase_08	AC	96 ms 17,292 KB
testcase_09	AC	99 ms 17,292 KB
testcase_10	AC	97 ms 17,284 KB
testcase_11	AC	95 ms 17,288 KB
testcase_12	AC	91 ms 17,164 KB
testcase_13	AC	94 ms 17,296 KB
testcase_14	AC	97 ms 17,280 KB
testcase_15	AC	93 ms 17,292 KB
testcase_16	AC	93 ms 17,296 KB
testcase_17	AC	92 ms 17,292 KB
testcase_18	AC	92 ms 17,288 KB
testcase_19	AC	95 ms 17,288 KB
testcase_20	AC	100 ms 17,288 KB
testcase_21	AC	100 ms 17,288 KB
testcase_22	AC	83 ms 21,060 KB
testcase_23	AC	83 ms 21,060 KB
testcase_24	AC	88 ms 21,060 KB
testcase_25	AC	84 ms 21,056 KB
testcase_26	AC	84 ms 20,928 KB
testcase_27	AC	82 ms 21,056 KB
testcase_28	AC	85 ms 21,056 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
/*-------------------------------------------------*/
using CostType = long long;
struct Edge {
  int src, dst; CostType cost;
  Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}
  inline bool operator<(const Edge &rhs) const {
    return cost != rhs.cost ? cost < rhs.cost : dst != rhs.dst ? dst < rhs.dst : src < rhs.src;
  }
  inline bool operator<=(const Edge &rhs) const { return cost <= rhs.cost; }
  inline bool operator>(const Edge &rhs) const {
    return cost != rhs.cost ? cost > rhs.cost : dst != rhs.dst ? dst > rhs.dst : src > rhs.src;
  }
  inline bool operator>=(const Edge &rhs) const { return cost >= rhs.cost; }
};

struct HLD {
  vector<int> parent, subtree, id, inv, head;
  vector<CostType> cost;

  HLD(const vector<vector<Edge> > &graph, int root = 0) : graph(graph) {
    int n = graph.size();
    parent.assign(n, -1);
    subtree.assign(n, 1);
    id.resize(n);
    inv.resize(n);
    head.resize(n);
    dfs1(root);
    head[root] = root;
    int now_id = 0;
    dfs2(root, now_id);
  }

  void v_update(int u, int v, const function<void(int, int)> &f) {
    while (true) {
      if (id[u] > id[v]) swap(u, v);
      f(max(id[head[v]], id[u]), id[v] + 1);
      if (head[u] == head[v]) return;
      v = parent[head[v]];
    }
  }

  template <typename T>
  T v_query(int u, int v, const function<T(int, int)> &f, const function<T(T, T)> &g, T &UNITY) {
    T left = UNITY, right = UNITY;
    while (true) {
      if (id[u] > id[v]) {
        swap(u, v);
        swap(left, right);
      }
      left = g(left, f(max(id[head[v]], id[u]), id[v] + 1));
      if (head[u] == head[v]) break;
      v = parent[head[v]];
    }
    return g(left, right);
  }

  void subtree_v_update(int v, const function<void(int, int)> &f) { f(id[v], id[v] + subtree[v]); }

  template <typename T>
  T subtree_v_query(int v, const function<T(int, int)> &f) { return f(id[v], id[v] + subtree[v]); }

  void e_update(int u, int v, const function<void(int, int)> &f) {
    while (true) {
      if (id[u] > id[v]) swap(u, v);
      if (head[u] == head[v]) {
        f(id[u], id[v]);
        break;
      } else {
        f(id[head[v]] - 1, id[v]);
        v = parent[head[v]];
      }
    }
  }

  template <typename T>
  T e_query(int u, int v, const function<T(int, int)> &f, const function<T(T, T)> &g, T &UNITY) {
    T left = UNITY, right = UNITY;
    while (true) {
      if (id[u] > id[v]) {
        swap(u, v);
        swap(left, right);
      }
      if (head[u] == head[v]) {
        left = g(left, f(id[u], id[v]));
        break;
      } else {
        left = g(left, f(id[head[v]] - 1, id[v]));
        v = parent[head[v]];
      }
    }
    return g(left, right);
  }

  void subtree_e_update(int v, const function<void(int, int)> &f) { f(id[v], id[v] + subtree[v] - 1); }

  template <typename T>
  T subtree_e_query(int v, const function<T(int, int)> &f) { return f(id[v], id[v] + subtree[v] - 1); }

  int lca(int u, int v) {
    while (true) {
      if (id[u] > id[v]) swap(u, v);
      if (head[u] == head[v]) return u;
      v = parent[head[v]];
    }
  }

private:
  vector<vector<Edge> > graph;

  void dfs1(int ver) {
    for (Edge &e : graph[ver]) if (e.dst != parent[ver]) {
      parent[e.dst] = ver;
      dfs1(e.dst);
      subtree[ver] += subtree[e.dst];
      if (subtree[e.dst] > subtree[graph[ver].front().dst]) swap(e, graph[ver].front());
    }
  }

  void dfs2(int ver, int &now_id) {
    id[ver] = now_id++;
    inv[id[ver]] = ver;
    for (Edge &e : graph[ver]) if (e.dst != parent[ver]) {
      head[e.dst] = (e.dst == graph[ver].front().dst ? head[ver] : e.dst);
      cost.emplace_back(e.cost);
      dfs2(e.dst, now_id);
    }
  }
};

template <typename Abelian>
struct BIT {
  BIT(int n_, const Abelian UNITY = 0) : n(n_), UNITY(UNITY) {
    ++n;
    dat_const.assign(n, UNITY);
    dat_linear.assign(n, UNITY);
  }

  void add(int left, int right, Abelian value) {
    for (int i = left; i < n; i += i & -i) {
      dat_const[i] -= value * (left - 1);
      dat_linear[i] += value;
    }
    for (int i = right + 1; i < n; i += i & -i) {
      dat_const[i] += value * right;
      dat_linear[i] -= value;
    }
  }

  Abelian sum(int idx) {
    Abelian res = UNITY;
    for (int i = idx; i > 0; i -= i & -i) res += dat_linear[i];
    res *= idx;
    for (int i = idx; i > 0; i -= i & -i) res += dat_const[i];
    return res;
  }

  Abelian sum(int left, int right) { return sum(right) - sum(left - 1); }

  Abelian operator[](const int idx) { return sum(idx, idx); }

private:
  int n;
  const Abelian UNITY;
  vector<Abelian> dat_const, dat_linear;
};

// https://onlinejudge.u-aizu.ac.jp/problems/2667
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<vector<Edge> > graph(n);
  REP(_, n - 1) {
    int u, v, w; cin >> u >> v >> w;
    graph[u].emplace_back(u, v, w);
  }
  HLD hld(graph, 0);
  BIT<long long> bit(n - 1);
  REP(i, n - 1) bit.add(i + 1, i + 1, hld.cost[i]);
  int q; cin >> q;
  while (q--) {
    int query; cin >> query;
    if (query == 1) {
      int a, x; cin >> a >> x;
      hld.subtree_e_update(a, [&](int lhs, int rhs) { return bit.add(lhs + 1, rhs, x); });
    } else if (query == 2) {
      int b; cin >> b;
      function<long long(int, int)> f = [&](int lhs, int rhs) { return bit.sum(lhs + 1, rhs); };
      function<long long(long long, long long)> g = [&](long long lhs, long long rhs) { return lhs + rhs; };
      long long UNITY = 0;
      cout << hld.e_query(0, b, f, g, UNITY) << '\n';
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード