Submission #605017

#	Time	Username	Problem	Language	Result	Execution time	Memory
605017		cadmiumsky	Magic Tree (CEOI19_magictree)	C++14	0 / 100	168 ms	72728 KiB

magictree

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using pii = pair<int,int>;
using ll = long long;

const int nmax = 1e5 + 5, inf = 1e9 + 5;
int n, m, k;

vector<int> g[nmax];

#define lsb(x) (x & -x)
namespace AIB {
  vector<ll> rez(1); int len = 0;
  void append(int n) {
    len += n;
    rez.resize(rez.size() + n); 
  }
  void upd(int x, int val) {
    while(x <= len)
      rez[x] += val,
       x += lsb(x);
  }
  int query(int x) {
    ll sum = 0;
    while(x > 0)
      sum += rez[x],
      x -= lsb(x);
    return min((ll)inf, sum);
  }
  int query(int l, int r) { return query(r) - query(l - 1); }
}
pii vec[nmax]; // zi, cost

int preord[nmax], pin[nmax], pout[nmax], inp = 1;

namespace AINT {
  vector<pii> list[nmax * 4];
  int left[nmax], right[nmax];
  void initAIB(int node = 1, int cl = 1, int cr = n) {
    left[node] = AIB::rez.size();
    AIB::append(cr - cl + 1);
    right[node] = AIB::rez.size() - 1;
    if(cl == cr)
      return;
    int mid = cl + cr >> 1;
    initAIB(2 * node, cl, mid);
    initAIB(2 * node + 1, mid + 1, cr);
  }
  void initAINT(int node = 1, int cl = 1, int cr = n) {
    if(cl == cr) {
      list[node].push_back(vec[preord[cl]]);
      AIB::upd(left[node], list[node].back().second);
      return;
    }
    int mid = cl + cr >> 1;
    initAINT(2 * node, cl, mid);
    initAINT(2 * node + 1, mid + 1, cr);
    int p[2] = {0, 0}, l = 2 * node, r = 2 * node + 1;
    while(p[0] < list[l].size()) {
      if(list[l][p[0]] > list[r][p[1]])
        swap(l, r),
        swap(p[0], p[1]);
      list[node].push_back(list[l][p[0]]);
      p[0]++;
    }
    while(p[1] < list[r].size())
      list[node].push_back(list[r][p[1]++]);
    for(int i = 0; i < list[node].size(); i++)
      AIB::upd(left[node] + i, list[node][i].second);
    return;
  }
  int query(int l, int r, int val, int node = 1, int cl = 1, int cr = n) {
    if(r < cl || cr < l)
      return 0;
    if(l <= cl && cr <= r)
      return AIB::query(upper_bound(all(list[node]), pii{val, inf}) - list[node].begin() + left[node], right[node]);
    int mid = cl + cr >> 1;
    return query(l, r, val, 2 * node, cl, mid) + query(l, r, val, 2 * node + 1, mid + 1, cr);
  }
  void voidpoz(int poz, int val, int node = 1, int cl = 1, int cr = n) {
    AIB::upd(lower_bound(all(list[node]), pii{val, 0}) - list[node].begin() + left[node], -val);
    if(cl == cr)
      return;
    int mid = cl + cr >> 1;
    if(poz <= mid)
      voidpoz(poz, val, 2 * node, cl, mid);
    else
      voidpoz(poz, val, 2 * node + 1, mid + 1, cr);
    return;
  }
};

static void initdfs(int node) {
  preord[inp] = node;
  pin[node] = inp++;
  for(auto x : g[node])
    initdfs(x);
  pout[node] = inp -1;
}

set<pii> elems[nmax];

static void dfs(int node) {
  //cerr << node << ' ' << "amog\n";
  for(auto x : g[node]) {
    dfs(x);
    if(elems[node].size() < elems[x].size())
      swap(elems[x], elems[node]);
    for(auto a : elems[x])
      elems[node].insert(a);
  }
  //cerr << "amog\n";
  int discrept = vec[node].second - AINT::query(pin[node], pout[node], vec[node].first);
  //cerr << node + 1 << ":\n";
  //cerr << AINT::query(pin[node], pout[node], vec[node].first) << ' ' << vec[node].second << ' ' << discrept << '\n';
  if(discrept >= 0) {
    //cerr << "sus\n";
    while(elems[node].size() && elems[node].rbegin() -> first > vec[node].first) {
      AINT::voidpoz(pin[elems[node].rbegin() -> second], vec[elems[node].rbegin() -> second].second);
      //cerr << "ok\n";
      elems[node].erase(*elems[node].rbegin());
    }
    elems[node].insert({vec[node].first, node});
  //cerr << "amogus\n";
  }
  else 
    //cerr << "susy\n",
    AINT::voidpoz(pin[node], vec[node].second);
    //cerr << "ok\n";
  //cerr << "amogii\n";
  //for(auto [a, b] : elems[node])
    //cerr << b << ' ' << vec[b].first << ' ' << vec[b].second << '\n';
  //cerr << "amog\n";
  return;
} 

int main() {
  cin >> n >> m >> k;
  for(int i = 0; i < n; i++) {
    vec[i] = pii{inf, 0};
  }
  AINT::initAIB();
  for(int x, i = 1; i < n; i++) {
    cin >> x;
    g[--x].push_back(i);
  }
  for(int i = 0, v, d, w; i < m; i++)
    cin >> v >> d >> w,
    vec[--v] = pii{d, w};
  initdfs(0);
  AINT::initAINT();
  dfs(0);
  cout << AINT::query(1, n, -1) << '\n';
}

Compilation message (stderr)

magictree.cpp: In function 'void AINT::initAIB(int, int, int)':
magictree.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
magictree.cpp: In function 'void AINT::initAINT(int, int, int)':
magictree.cpp:56:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
magictree.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     while(p[0] < list[l].size()) {
      |           ~~~~~^~~~~~~~~~~~~~~~
magictree.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while(p[1] < list[r].size())
      |           ~~~~~^~~~~~~~~~~~~~~~
magictree.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < list[node].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~
magictree.cpp: In function 'int AINT::query(int, int, int, int, int, int)':
magictree.cpp:78:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
magictree.cpp: In function 'void AINT::voidpoz(int, int, int, int, int)':
magictree.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = cl + cr >> 1;
      |               ~~~^~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17