Submission #1201207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201207		vidux	Tree (IOI24_tree)	C++17	17 / 100	2095 ms	17684 KiB

tree

#include <bits/stdc++.h>
using namespace std;

//#define LOCAL

#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

const int INF = 1e9;
const ll LLINF = 1e18;

vi p, w;
vvi child;
ll leafs;
bool t5;

void init(std::vector<int> P, std::vector<int> W) {
	p = P;
	w = W;
	int n = SZ(w);
	t5 = 1;
	FOR(i, n) if (w[i] != 1) { t5 = 0; break; }
	child = vvi(SZ(p));
	REP(i, 1, SZ(p)-1) {
		child[p[i]].push_back(i);
	}
	leafs = 0;
	FOR(i, n) if (SZ(child[i]) == 0) leafs++;
}

long long query(int L, int R) {
	if (t5 == 1) {
		ll ans = leafs*L;
		if (ans > R) ans += ans - R;
		return ans;
	}
	ll ans = 0;
	auto dfs = [&](int i, auto dfs) -> ll {
		if (SZ(child[i]) == 0) {
			ans += ((ll)L) * (ll)w[i];
			return L;
		}
		ll sum = 0;
		FORR(j, child[i]) sum += dfs(j, dfs);
		if (sum > R) {
			ans += (sum - (ll)R) * (ll)w[i];
			sum = R;
		}
		return sum;
	};
	ll extra = dfs(0, dfs);
	if (extra > R) ans += (extra - (ll)R) * (ll)w[0];
	return ans;
}

#ifdef LOCAL
int main() {
	init({-1, 0, 0}, {1, 1, 1});
	cout << query(1, 1) << endl;
	cout << query(1, 2) << endl;
    return 0;
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19