oj.uz

Submission #791642

# Submission time Handle Problem Language Result Execution time Memory
791642 2023-07-24T08:27:40 Z GEN 이지후(#10078) Nestabilnost (COI23_nestabilnost) C++17
61 / 100
 1500 ms 100548 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 make_pair(canGeq, val) < make_pair(nd.canGeq, 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 eqs
	{
		vector<int> coords;
		for (auto &v : aggr) {
			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) {
				lint minv = 1e18;
				for (auto &j : v) {
					if (j.canGeq && j.val <= x)
						minv = min(minv, j.cost);
					if (!j.canGeq && j.val == x)
						minv = min(minv, j.cost);
				}
				tot += minv;
				if (tot > 1e18)
					tot = 1e18;
			}
			if (tot < 1e17)
				ret.push_back({x, 0, tot});
		}
	}
	// 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});
				}
			}
		}
		sort(all(upd));
		lint t1 = 1e17;
		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++) {
				costPoses[upd[k][2]] = min(costPoses[upd[k][2]], upd[k][1]);
			}
			lint sum = 0;
			for (int x = 0; x < sz(aggr); x++) {
				sum += costPoses[x];
				if (sum > 1e18)
					break;
			}
			if (t1 > sum) {
				t1 = sum;
				ret.push_back({(int)upd[i][0], 1, t1});
			}
			i = j;
		}
	}
	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 6 ms 8804 KB Output is correct
3 Correct 7 ms 8816 KB Output is correct
4 Correct 7 ms 8784 KB Output is correct
5 Correct 6 ms 8056 KB Output is correct
6 Correct 7 ms 8020 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 96624 KB Output is correct
2 Correct 205 ms 99660 KB Output is correct
3 Correct 216 ms 100052 KB Output is correct
4 Correct 214 ms 100548 KB Output is correct
5 Correct 192 ms 99600 KB Output is correct
6 Correct 173 ms 47948 KB Output is correct
7 Correct 170 ms 48240 KB Output is correct
8 Correct 175 ms 48972 KB Output is correct
9 Correct 170 ms 49100 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7400 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7396 KB Output is correct
7 Correct 3 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 6 ms 8804 KB Output is correct
3 Correct 7 ms 8816 KB Output is correct
4 Correct 7 ms 8784 KB Output is correct
5 Correct 6 ms 8056 KB Output is correct
6 Correct 7 ms 8020 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7400 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 3 ms 7380 KB Output is correct
11 Correct 3 ms 7380 KB Output is correct
12 Correct 3 ms 7396 KB Output is correct
13 Correct 3 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 6 ms 7636 KB Output is correct
17 Correct 9 ms 7792 KB Output is correct
18 Correct 6 ms 7764 KB Output is correct
19 Correct 6 ms 7764 KB Output is correct
20 Correct 6 ms 7636 KB Output is correct
21 Correct 5 ms 7760 KB Output is correct
22 Correct 6 ms 7760 KB Output is correct
23 Correct 6 ms 7720 KB Output is correct
24 Correct 97 ms 7972 KB Output is correct
25 Correct 126 ms 7956 KB Output is correct
26 Correct 209 ms 8028 KB Output is correct
27 Correct 345 ms 8020 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 6 ms 8804 KB Output is correct
3 Correct 7 ms 8816 KB Output is correct
4 Correct 7 ms 8784 KB Output is correct
5 Correct 6 ms 8056 KB Output is correct
6 Correct 7 ms 8020 KB Output is correct
7 Correct 184 ms 96624 KB Output is correct
8 Correct 205 ms 99660 KB Output is correct
9 Correct 216 ms 100052 KB Output is correct
10 Correct 214 ms 100548 KB Output is correct
11 Correct 192 ms 99600 KB Output is correct
12 Correct 173 ms 47948 KB Output is correct
13 Correct 170 ms 48240 KB Output is correct
14 Correct 175 ms 48972 KB Output is correct
15 Correct 170 ms 49100 KB Output is correct
16 Correct 3 ms 7380 KB Output is correct
17 Correct 3 ms 7400 KB Output is correct
18 Correct 3 ms 7380 KB Output is correct
19 Correct 3 ms 7380 KB Output is correct
20 Correct 3 ms 7380 KB Output is correct
21 Correct 3 ms 7396 KB Output is correct
22 Correct 3 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 6 ms 7636 KB Output is correct
26 Correct 9 ms 7792 KB Output is correct
27 Correct 6 ms 7764 KB Output is correct
28 Correct 6 ms 7764 KB Output is correct
29 Correct 6 ms 7636 KB Output is correct
30 Correct 5 ms 7760 KB Output is correct
31 Correct 6 ms 7760 KB Output is correct
32 Correct 6 ms 7720 KB Output is correct
33 Correct 97 ms 7972 KB Output is correct
34 Correct 126 ms 7956 KB Output is correct
35 Correct 209 ms 8028 KB Output is correct
36 Correct 345 ms 8020 KB Output is correct
37 Correct 269 ms 29588 KB Output is correct
38 Correct 271 ms 29616 KB Output is correct
39 Correct 261 ms 30348 KB Output is correct
40 Correct 277 ms 30656 KB Output is correct
41 Correct 264 ms 29500 KB Output is correct
42 Correct 256 ms 29484 KB Output is correct
43 Correct 268 ms 29924 KB Output is correct
44 Correct 261 ms 31508 KB Output is correct
45 Correct 312 ms 35372 KB Output is correct
46 Correct 217 ms 29900 KB Output is correct
47 Correct 209 ms 30304 KB Output is correct
48 Correct 218 ms 30328 KB Output is correct
49 Correct 210 ms 30292 KB Output is correct
50 Execution timed out 1566 ms 40480 KB Time limit exceeded
51 Halted 0 ms 0 KB -