oj.uz

Submission #791653

# Submission time Handle Problem Language Result Execution time Memory
791653 2023-07-24T08:34:26 Z GEN 이지후(#10078) Nestabilnost (COI23_nestabilnost) C++17
61 / 100
 354 ms 96592 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 a[MAXN], f[MAXN], sm[MAXN], 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 node {
	int val;
	int canGeq;
	lint cost;
	lint eval() { return cost + (canGeq ? sm[val] : f[val]); }
	bool operator<(const node &nd) const { return val < nd.val; }
};

vector<node> solve(int x, int p) {
	vector<vector<node>> aggr;
	for (auto &y : gph[x]) {
		if (y != p && !root[y]) {
			auto v = solve(y, x);
			if (a[x] + 1 == a[y]) {
				lint totmin = 1e18;
				for (auto &x : v)
					totmin = min(totmin, x.eval());
				v.push_back({0, 1, totmin});
			} else {
				lint costEq = 1e18;
				lint totmin = 1e18;
				for (auto &foo : v) {
					if (foo.val == a[x] + 1 || (foo.val <= a[x] + 1 && foo.canGeq)) {
						costEq = min(costEq, foo.cost);
					}
					totmin = min(totmin, foo.eval());
				}
				v.clear();
				v.push_back({0, 1, totmin});
				v.push_back({a[x] + 1, 0, costEq});
				// k = a[x] + 1 or k >= 0
			}
			aggr.push_back(v);
		}
	}
	if (sz(aggr) == 0) {
		vector<node> ret;
		ret.push_back({a[x] + 1, 1, 0});
		return ret;
	}
	vector<node> ret;
	// generate geqs
	{
		vector<lint> costPoses(sz(aggr), 1e18);
		vector<array<lint, 3>> upd;
		for (int i = 0; i < sz(aggr); i++) {
			for (auto &y : aggr[i]) {
				if (y.canGeq) {
					upd.push_back({max(y.val, a[x] + 1), y.cost, i});
				}
			}
		}
		int toolarge = sz(aggr);
		sort(all(upd));
		lint t1 = 1e17;
		lint sum = 0;
		for (int i = 0; i < sz(upd);) {
			int j = i;
			while (j < sz(upd) && upd[j][0] == upd[i][0])
				j++;
			for (int k = i; k < j; k++) {
				if (costPoses[upd[k][2]] > 5e17) {
					toolarge--;
					sum += upd[k][1];
				} else {
					if (costPoses[upd[k][2]] > upd[k][1]) {
						sum += upd[k][1] - costPoses[upd[k][2]];
					}
				}
				costPoses[upd[k][2]] = min(costPoses[upd[k][2]], upd[k][1]);
			}
			if (toolarge) {
				i = j;
				continue;
			}
			if (t1 > sum) {
				t1 = sum;
				ret.push_back({(int)upd[i][0], 1, t1});
			}
			i = j;
		}
	}
	// generate eqs (mutate if u like it)
	{
		vector<int> coords;
		for (auto &v : aggr) {
			sort(all(v));
			for (auto &y : v) {
				if (y.canGeq == 0 && y.val > a[x])
					coords.push_back(y.val);
			}
		}
		sort(all(coords));
		coords.resize(unique(all(coords)) - coords.begin());
		for (auto &x : coords) {
			lint tot = 0;
			for (auto &v : aggr) {
				int pos = upper_bound(all(v), (node){x, 0, 0}) - v.begin();
				lint minv = 1e18;
				for (int j = pos - 1; j >= max(0, pos - 3); j--) {
					if (v[j].canGeq)
						minv = min(minv, v[j].cost);
					else if (!v[j].canGeq && v[j].val == x)
						minv = min(minv, v[j].cost);
				}
				tot += minv;
				if (tot > 1e18) {
					break;
				}
			}
			if (tot < 1e17)
				ret.push_back({x, 0, tot});
		}
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	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] = 1e9;
	for (int i = n; i; i--) {
		sm[i] = min(sm[i + 1], 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]) {
			auto foo = solve(i, par[i]);
			lint tot = 1e18;
			for (auto &x : foo)
				tot = min(tot, x.eval());
			ans += tot;
		}
	}
	cout << ans << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8788 KB Output is correct
2 Correct 7 ms 8804 KB Output is correct
3 Correct 7 ms 8788 KB Output is correct
4 Correct 6 ms 8820 KB Output is correct
5 Correct 6 ms 7892 KB Output is correct
6 Correct 6 ms 7892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 96592 KB Output is correct
2 Correct 207 ms 96460 KB Output is correct
3 Correct 233 ms 96504 KB Output is correct
4 Correct 221 ms 96556 KB Output is correct
5 Correct 210 ms 96524 KB Output is correct
6 Correct 190 ms 40172 KB Output is correct
7 Correct 223 ms 40480 KB Output is correct
8 Correct 180 ms 41356 KB Output is correct
9 Correct 179 ms 41380 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7316 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8788 KB Output is correct
2 Correct 7 ms 8804 KB Output is correct
3 Correct 7 ms 8788 KB Output is correct
4 Correct 6 ms 8820 KB Output is correct
5 Correct 6 ms 7892 KB Output is correct
6 Correct 6 ms 7892 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 3 ms 7316 KB Output is correct
11 Correct 3 ms 7380 KB Output is correct
12 Correct 3 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 6 ms 7636 KB Output is correct
15 Correct 6 ms 7636 KB Output is correct
16 Correct 7 ms 7556 KB Output is correct
17 Correct 6 ms 7636 KB Output is correct
18 Correct 6 ms 7636 KB Output is correct
19 Correct 6 ms 7740 KB Output is correct
20 Correct 8 ms 7636 KB Output is correct
21 Correct 6 ms 7544 KB Output is correct
22 Correct 5 ms 7636 KB Output is correct
23 Correct 6 ms 7636 KB Output is correct
24 Correct 21 ms 7888 KB Output is correct
25 Correct 24 ms 7892 KB Output is correct
26 Correct 33 ms 7928 KB Output is correct
27 Correct 46 ms 7988 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8788 KB Output is correct
2 Correct 7 ms 8804 KB Output is correct
3 Correct 7 ms 8788 KB Output is correct
4 Correct 6 ms 8820 KB Output is correct
5 Correct 6 ms 7892 KB Output is correct
6 Correct 6 ms 7892 KB Output is correct
7 Correct 212 ms 96592 KB Output is correct
8 Correct 207 ms 96460 KB Output is correct
9 Correct 233 ms 96504 KB Output is correct
10 Correct 221 ms 96556 KB Output is correct
11 Correct 210 ms 96524 KB Output is correct
12 Correct 190 ms 40172 KB Output is correct
13 Correct 223 ms 40480 KB Output is correct
14 Correct 180 ms 41356 KB Output is correct
15 Correct 179 ms 41380 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 3 ms 7380 KB Output is correct
18 Correct 3 ms 7380 KB Output is correct
19 Correct 3 ms 7316 KB Output is correct
20 Correct 3 ms 7380 KB Output is correct
21 Correct 3 ms 7380 KB Output is correct
22 Correct 4 ms 7380 KB Output is correct
23 Correct 6 ms 7636 KB Output is correct
24 Correct 6 ms 7636 KB Output is correct
25 Correct 7 ms 7556 KB Output is correct
26 Correct 6 ms 7636 KB Output is correct
27 Correct 6 ms 7636 KB Output is correct
28 Correct 6 ms 7740 KB Output is correct
29 Correct 8 ms 7636 KB Output is correct
30 Correct 6 ms 7544 KB Output is correct
31 Correct 5 ms 7636 KB Output is correct
32 Correct 6 ms 7636 KB Output is correct
33 Correct 21 ms 7888 KB Output is correct
34 Correct 24 ms 7892 KB Output is correct
35 Correct 33 ms 7928 KB Output is correct
36 Correct 46 ms 7988 KB Output is correct
37 Correct 242 ms 21788 KB Output is correct
38 Correct 289 ms 21928 KB Output is correct
39 Correct 354 ms 21796 KB Output is correct
40 Correct 285 ms 21804 KB Output is correct
41 Correct 275 ms 21808 KB Output is correct
42 Correct 277 ms 21740 KB Output is correct
43 Correct 290 ms 22272 KB Output is correct
44 Correct 283 ms 23792 KB Output is correct
45 Incorrect 285 ms 27644 KB Output isn't correct
46 Halted 0 ms 0 KB -