Submission #392320

#	Time	Username	Problem	Language	Result	Execution time	Memory
392320		MiricaMatei	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	417 ms	81492 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;
const int inf = 2000000000;

struct slope_trick {
  map<int, long long> delta;

  slope_trick () {
    delta = map<int, long long>();
  }

  void mergeDelta(slope_trick other) {
    for (auto it:other.delta)
      delta[it.first] += it.second;
    other.delta.clear();
  }

  void add(int x, long long val) {
    delta[-inf] += val;
    delta[x] -= val;
    delta[x + 1] += val;

    map<int, long long>::iterator it1, it2;
    it1 = delta.lower_bound(x);

    val = delta[x];
    while (val < 0) {
      it2 = it1;
      it1--;
      delta.erase(it2);
      val = it1->second + val;
      it1->second = val;
    }
  }
    int mapSize() {
      return delta.size();
    }

    long long query() {
      return delta[-inf];
    }
};

vector<int>G[MAXN];

int a[MAXN], h[MAXN], c[MAXN];

slope_trick dfs(int node) {
  slope_trick ans;
  for (auto it:G[node]) {
    slope_trick aux = dfs(it);
    if (aux.mapSize() > ans.mapSize())
      swap(ans, aux);
    ans.mergeDelta(aux);
  }
  ans.add(h[node], c[node]);
  return ans;
}

long long solve(int node) {
  slope_trick ans = dfs(node);
  return ans.query();
}

int main() {
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  int N;
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%d%d%d", &a[i], &h[i], &c[i]);
    if (i > 1)
      G[a[i]].push_back(i);
  }

  long long ans = solve(1);

  printf("%lld\n", ans);

  return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   scanf("%d", &N);
      |   ~~~~~^~~~~~~~~~
worst_reporter2.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("%d%d%d", &a[i], &h[i], &c[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21