oj.uz

답안 #943436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943436 2024-03-11T13:11:16 Z marvinthang Arboras (RMI20_arboras) C++17
100 / 100
 132 ms 19204 KB 
/*************************************
*    author: marvinthang             *
*    created: 11.03.2024 18:56:24    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

// end of template

const int MOD = 1e9 + 7;

void process(void) {
	int n; cin >> n;
	vector <int> par(n);
	vector <long long> lengths(n);
	vector <vector <int>> adj(n);
	FOR(i, 1, n) {
		cin >> par[i];
		adj[par[i]].push_back(i);
	}
	FOR(i, 1, n) cin >> lengths[i];
	vector <int> tin(n), tout(n), depth(n), val(n), pos(n);
	long long res = 0;
	function<pair <long long, int>(int)> dfs = [&] (int u) {
		static int t = 0;
		val[t] = u;
		tin[u] = t++;
		pair <long long, int> cur(lengths[u], u);
		long long se = lengths[u];
		for (int v: adj[u]) {
			lengths[v] += lengths[u];
			depth[v] = depth[u] + 1;
			pair <long long, int> val = dfs(v);
			if (cur < val) {
				se = cur.fi;
				cur = val;
			} else maximize(se, val.fi);
		}
		res += cur.fi + se - 2 * lengths[u];
		tout[u] = t;
		pos[cur.se] = u;
		return cur;
	};
	dfs(0);
	vector <pair <long long, int>> st(n + n);
	vector <long long> lazy(n);
	int h = __lg(n + n - 1);
	REP(i, n) st[i + n] = pair{lengths[val[i]], val[i]};
	FORD(i, n, 1) st[i] = max(st[i << 1], st[i << 1 | 1]);
	auto apply = [&] (int i, long long val) {
		st[i].fi += val;
		if (i < n) lazy[i] += val;
	};
	auto pushUp = [&] (int i) {
		while (i >>= 1) {
			st[i] = max(st[i << 1], st[i << 1 | 1]);
			st[i].fi += lazy[i];
		}
	};
	auto pushDown = [&] (int p) {
		FORD(s, h, 1) {
			int i = p >> s;
			if (lazy[i]) {
				apply(i << 1, lazy[i]);
				apply(i << 1 | 1, lazy[i]);
				lazy[i] = 0;
			}
		}
	};
	auto update = [&] (int l0, int r0, int val) {
		l0 += n; r0 += n;
		for (int l = l0, r = r0; l < r; l >>= 1, r >>= 1) {
			if (l & 1) apply(l++, val);
			if (r & 1) apply(--r, val);
		}
		pushUp(l0);	
		if (l0 + 1 != r0) pushUp(r0 - 1);
	};
	auto getMax = [&] (int l, int r) {
		l += n; r += n;
		pushDown(l); 
		if (l + 1 != r) pushDown(r - 1);
		pair <long long, int> res(0, -1);
		for (; l < r; l >>= 1, r >>= 1) {
			if (l & 1) maximize(res, st[l++]);
			if (r & 1) maximize(res, st[--r]);
		}
		return res;
	};
	res %= MOD;
	cout << res << '\n';
	int q; cin >> q;
	while (q--) {
		int u, add; cin >> u >> add;
		pair <long long, int> cur = getMax(tin[u], tout[u]);
		cur.fi += add;
		int p = pos[cur.se];
		res += 1LL * (depth[u] - depth[p]) * add;
		while (p) {
			pair <long long, int> fip = getMax(tin[par[p]], tout[par[p]]);
			int child = *prev(partition_point(ALL(adj[par[p]]), [&] (int x) { return tin[x] <= tin[fip.se]; }));
			pair <long long, int> sep = max(getMax(tin[par[p]], tin[child]), getMax(tout[child], tout[par[p]]));
			if (cur > fip) {
				int w = pos[fip.se];
				res += 1LL * (depth[p] - depth[w]) * (cur.fi - fip.fi) + fip.fi - sep.fi;
				pos[fip.se] = child;
				p = w;
			} else {
				if (cur > sep) res += cur.fi - sep.fi;
				break;
			}
		}
		pos[cur.se] = p;
		update(tin[u], tout[u], add);
		res %= MOD;
		if (res < 0) res += MOD;
		cout << res << '\n';
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("arboras");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

arboras.cpp: In function 'int main()':
arboras.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
arboras.cpp:160:2: note: in expansion of macro 'file'
  160 |  file("arboras");
      |  ^~~~
arboras.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
arboras.cpp:160:2: note: in expansion of macro 'file'
  160 |  file("arboras");
      |  ^~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 12380 KB Output is correct
2 Correct 74 ms 11196 KB Output is correct
3 Correct 70 ms 11220 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 14672 KB Output is correct
2 Correct 84 ms 18168 KB Output is correct
3 Correct 92 ms 12524 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 119 ms 12380 KB Output is correct
5 Correct 74 ms 11196 KB Output is correct
6 Correct 70 ms 11220 KB Output is correct
7 Correct 132 ms 14672 KB Output is correct
8 Correct 84 ms 18168 KB Output is correct
9 Correct 92 ms 12524 KB Output is correct
10 Correct 110 ms 14832 KB Output is correct
11 Correct 84 ms 18196 KB Output is correct
12 Correct 102 ms 12628 KB Output is correct
13 Correct 67 ms 18260 KB Output is correct
14 Correct 70 ms 19204 KB Output is correct