oj.uz

Submission #791823

# Submission time Handle Problem Language Result Execution time Memory
791823 2023-07-24T10:35:30 Z GEN 이지후(#10078) Nestabilnost (COI23_nestabilnost) C++17
61 / 100
 1500 ms 128144 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 300005;

int n, a[MAXN], f[MAXN];
lint sm[MAXN];
int par[MAXN];
int root[MAXN];
vector<int> gph[MAXN];

void dfs(int x, int p) {
	if (p == -1)
		root[x] = 1, par[x] = -1;
	for (auto &y : gph[x]) {
		if (y != p) {
			if (a[y] <= a[x] && a[y] > 0)
				root[y] = 1;
			if (a[y] > a[x] + 1)
				root[y] = 1;
			par[y] = x;
			dfs(y, x);
		}
	}
}

struct DP {
	map<lint, lint> incrBy;
	map<lint, lint> equals;
	pair<lint, lint> totMin() {
		lint totmin = 1e18;
		lint sum = 0;
		{
			auto it = incrBy.end();
			while (it != incrBy.begin()) {
				it--;
				totmin = min(totmin, sum + sm[(*it).first + 1]);
				sum += (*it).second;
			}
			totmin = min(totmin, sum + sm[1]);
		}
		{
			auto it1 = equals.end();
			auto it2 = incrBy.end();
			lint sum = 0;
			while (it1 != equals.begin()) {
				it1--;
				while (it2 != incrBy.begin() && (*prev(it2)).first >= (*it1).first) {
					it2--;
					sum += it2->second;
				}
				totmin = min(totmin, f[it1->first] - it1->second + sum);
			}
		}
		return make_pair(totmin, sum);
	}
	void print() {
		return;
		cout << "incrBy" << endl;
		for (auto &[k, v] : incrBy)
			cout << k << " " << v << endl;
		cout << "equals" << endl;
		for (auto &[k, v] : equals)
			cout << k << " " << v << endl;
		auto [tot, sum] = totMin();
		cout << "totmin = " << tot << " sum = " << sum << endl;
	}
};

DP v[MAXN];
int idx[MAXN];

void solve(int x, int p) {
	idx[x] = x;
	vector<int> down;
	for (auto &y : gph[x]) {
		if (y != p && !root[y]) {
			solve(y, x);
			if (a[x] + 1 == a[y]) {
				auto [totmin, sum] = v[idx[y]].totMin();
				auto it1 = v[idx[y]].incrBy.begin();
				auto it2 = v[idx[y]].equals.begin();
				while (totmin < sum) {
					lint delta = sum - totmin;
					auto val = *it1;
					it1 = v[idx[y]].incrBy.erase(it1);
					sum -= min(val.second, delta);
					val.second -= min(val.second, delta);
					if (val.second)
						v[idx[y]].incrBy.insert(val);
					while (it2 != v[idx[y]].equals.end() && it2->first <= val.first) {
						if (it2->second <= delta) {
							it2 = v[idx[y]].equals.erase(it2);
						} else {
							auto val = *it2;
							val.second -= delta;
							v[idx[y]].equals.erase(it2);
							v[idx[y]].equals.insert(val);
							it2 = v[idx[y]].equals.upper_bound(val.first);
						}
					}
				}
			} else {
				auto [totmin, sum] = v[idx[y]].totMin();
				lint costEq = 0;
				{
					auto it = v[idx[y]].incrBy.end();
					while (it != v[idx[y]].incrBy.begin()) {
						it--;
						if (it->first >= a[x] + 1)
							costEq += it->second;
						else
							break;
					}
				}
				if (v[idx[y]].equals.count(a[x] + 1))
					costEq -= v[idx[y]].equals[a[x] + 1];
				v[idx[y]].incrBy.clear();
				v[idx[y]].equals.clear();
				if (totmin > costEq)
					v[idx[y]].equals[a[x] + 1] = totmin - costEq;
				v[idx[y]].incrBy[n] = totmin;
			}
			down.push_back(idx[y]);
		}
	}
	if (sz(down) == 0) {
		v[idx[x]].incrBy[a[x]] = 1e18;
		return;
	}
	sort(all(down), [&](int p, int q) { return sz(v[p].equals) + sz(v[p].incrBy) > sz(v[q].equals) + sz(v[q].incrBy); });
	idx[x] = down[0];
	// generate geqs
	{
		for (int i = 1; i < sz(down); i++) {
			for (auto &[k, va] : v[down[i]].incrBy) {
				if (k > a[x])
					v[idx[x]].incrBy[k] += va;
			}
			for (auto &[k, va] : v[down[i]].equals) {
				if (k > a[x])
					v[idx[x]].equals[k] += va;
			}
		}
	}
	// generate eqs (mutate if u like it)
	{
		auto it = v[idx[x]].incrBy.begin();
		while (it != v[idx[x]].incrBy.end()) {
			if (it->first <= a[x]) {
				it = v[idx[x]].incrBy.erase(it);
			} else
				break;
		}
	}
	{
		auto it = v[idx[x]].equals.begin();
		while (it != v[idx[x]].equals.end()) {
			if (it->first <= a[x]) {
				it = v[idx[x]].equals.erase(it);
			} else
				break;
		}
	}
	v[idx[x]].incrBy[a[x]] = 1e18;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> f[i];
	}
	sm[n + 1] = 1e18;
	for (int i = n; i; i--) {
		sm[i] = min(sm[i + 1], 1ll * f[i]);
	}
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		gph[u].push_back(v);
		gph[v].push_back(u);
	}
	dfs(0, -1);
	lint ans = 0;
	for (int i = 0; i < n; i++) {
		if (root[i]) {
			solve(i, par[i]);
			lint totmin = v[idx[i]].totMin().first;
			ans += totmin;
		}
	}
	cout << ans << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37108 KB Output is correct
2 Correct 21 ms 37204 KB Output is correct
3 Correct 23 ms 37216 KB Output is correct
4 Correct 21 ms 37132 KB Output is correct
5 Correct 20 ms 36300 KB Output is correct
6 Correct 20 ms 36308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 127796 KB Output is correct
2 Correct 182 ms 128144 KB Output is correct
3 Correct 185 ms 127872 KB Output is correct
4 Correct 183 ms 127884 KB Output is correct
5 Correct 185 ms 127860 KB Output is correct
6 Correct 202 ms 71460 KB Output is correct
7 Correct 166 ms 71828 KB Output is correct
8 Correct 159 ms 72792 KB Output is correct
9 Correct 162 ms 74416 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35512 KB Output is correct
2 Correct 18 ms 35480 KB Output is correct
3 Correct 19 ms 35532 KB Output is correct
4 Correct 18 ms 35564 KB Output is correct
5 Correct 18 ms 35536 KB Output is correct
6 Correct 18 ms 35560 KB Output is correct
7 Correct 19 ms 35540 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37108 KB Output is correct
2 Correct 21 ms 37204 KB Output is correct
3 Correct 23 ms 37216 KB Output is correct
4 Correct 21 ms 37132 KB Output is correct
5 Correct 20 ms 36300 KB Output is correct
6 Correct 20 ms 36308 KB Output is correct
7 Correct 19 ms 35512 KB Output is correct
8 Correct 18 ms 35480 KB Output is correct
9 Correct 19 ms 35532 KB Output is correct
10 Correct 18 ms 35564 KB Output is correct
11 Correct 18 ms 35536 KB Output is correct
12 Correct 18 ms 35560 KB Output is correct
13 Correct 19 ms 35540 KB Output is correct
14 Correct 23 ms 36116 KB Output is correct
15 Correct 23 ms 36232 KB Output is correct
16 Correct 22 ms 36092 KB Output is correct
17 Correct 22 ms 36180 KB Output is correct
18 Correct 22 ms 36228 KB Output is correct
19 Correct 25 ms 36216 KB Output is correct
20 Correct 21 ms 36268 KB Output is correct
21 Correct 25 ms 36232 KB Output is correct
22 Correct 22 ms 36308 KB Output is correct
23 Correct 21 ms 36332 KB Output is correct
24 Correct 24 ms 36372 KB Output is correct
25 Correct 26 ms 36468 KB Output is correct
26 Correct 25 ms 36596 KB Output is correct
27 Correct 25 ms 36436 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37108 KB Output is correct
2 Correct 21 ms 37204 KB Output is correct
3 Correct 23 ms 37216 KB Output is correct
4 Correct 21 ms 37132 KB Output is correct
5 Correct 20 ms 36300 KB Output is correct
6 Correct 20 ms 36308 KB Output is correct
7 Correct 199 ms 127796 KB Output is correct
8 Correct 182 ms 128144 KB Output is correct
9 Correct 185 ms 127872 KB Output is correct
10 Correct 183 ms 127884 KB Output is correct
11 Correct 185 ms 127860 KB Output is correct
12 Correct 202 ms 71460 KB Output is correct
13 Correct 166 ms 71828 KB Output is correct
14 Correct 159 ms 72792 KB Output is correct
15 Correct 162 ms 74416 KB Output is correct
16 Correct 19 ms 35512 KB Output is correct
17 Correct 18 ms 35480 KB Output is correct
18 Correct 19 ms 35532 KB Output is correct
19 Correct 18 ms 35564 KB Output is correct
20 Correct 18 ms 35536 KB Output is correct
21 Correct 18 ms 35560 KB Output is correct
22 Correct 19 ms 35540 KB Output is correct
23 Correct 23 ms 36116 KB Output is correct
24 Correct 23 ms 36232 KB Output is correct
25 Correct 22 ms 36092 KB Output is correct
26 Correct 22 ms 36180 KB Output is correct
27 Correct 22 ms 36228 KB Output is correct
28 Correct 25 ms 36216 KB Output is correct
29 Correct 21 ms 36268 KB Output is correct
30 Correct 25 ms 36232 KB Output is correct
31 Correct 22 ms 36308 KB Output is correct
32 Correct 21 ms 36332 KB Output is correct
33 Correct 24 ms 36372 KB Output is correct
34 Correct 26 ms 36468 KB Output is correct
35 Correct 25 ms 36596 KB Output is correct
36 Correct 25 ms 36436 KB Output is correct
37 Correct 353 ms 71500 KB Output is correct
38 Correct 379 ms 63392 KB Output is correct
39 Correct 357 ms 62220 KB Output is correct
40 Correct 354 ms 62144 KB Output is correct
41 Correct 336 ms 69600 KB Output is correct
42 Correct 334 ms 68292 KB Output is correct
43 Correct 341 ms 68672 KB Output is correct
44 Correct 346 ms 71072 KB Output is correct
45 Correct 365 ms 74168 KB Output is correct
46 Correct 319 ms 74228 KB Output is correct
47 Correct 401 ms 75144 KB Output is correct
48 Correct 295 ms 75464 KB Output is correct
49 Correct 288 ms 75228 KB Output is correct
50 Execution timed out 1571 ms 70568 KB Time limit exceeded
51 Halted 0 ms 0 KB -