oj.uz

답안 #791826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791826 2023-07-24T10:38:52 Z GEN 이지후(#10078) Nestabilnost (COI23_nestabilnost) C++17
61 / 100
 1500 ms 128020 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;

namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
	char num[40000];
	constexpr Pre() : num() {
		for (int i = 0; i < 10000; i++) {
			int n = i;
			for (int j = 3; j >= 0; j--) {
				num[i * 4 + j] = n % 10 + '0';
				n /= 10;
			}
		}
	}
} constexpr pre;

__attribute__((target("avx2"), optimize("O3"))) inline void load() {
	memcpy(ibuf, ibuf + pil, pir - pil);
	pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
	pil = 0;
}

__attribute__((target("avx2"), optimize("O3"))) inline void flush() {
	fwrite(obuf, 1, por, stdout);
	por = 0;
}

inline void rd(char &c) { c = ibuf[pil++]; }

template <typename T> __attribute__((target("avx2"), optimize("O3"))) inline void rd(T &x) {
	if (pil + 32 > pir)
		load();
	char c;
	do
		rd(c);
	while (c < '-');
	bool minus = 0;
	if constexpr (is_signed<T>::value) {
		if (c == '-') {
			minus = 1;
			rd(c);
		}
	}
	x = 0;
	while (c >= '0') {
		x = x * 10 + (c & 15);
		rd(c);
	}
	if constexpr (is_signed<T>::value) {
		if (minus)
			x = -x;
	}
}

inline void wt(char c) { obuf[por++] = c; }
template <typename T> __attribute__((target("avx2"), optimize("O3"))) inline void wt(T x) {
	if (por + 32 > SZ)
		flush();
	if (!x) {
		wt('0');
		return;
	}
	if constexpr (is_signed<T>::value) {
		if (x < 0) {
			wt('-');
			x = -x;
		}
	}
	if (x >= 10000000000000000) {
		uint32_t r1 = x % 100000000;
		uint64_t q1 = x / 100000000;
		if (x >= 1000000000000000000) {
			uint32_t n1 = r1 % 10000;
			uint32_t n2 = r1 / 10000;
			uint32_t n3 = q1 % 10000;
			uint32_t r2 = q1 / 10000;
			uint32_t n4 = r2 % 10000;
			uint32_t q2 = r2 / 10000;
			memcpy(obuf + por + 15, pre.num + (n1 << 2), 4);
			memcpy(obuf + por + 11, pre.num + (n2 << 2), 4);
			memcpy(obuf + por + 7, pre.num + (n3 << 2), 4);
			memcpy(obuf + por + 3, pre.num + (n4 << 2), 4);
			memcpy(obuf + por, pre.num + (q2 << 2) + 1, 3);
			por += 19;
		} else if (x >= 100000000000000000) {
			uint32_t n1 = r1 % 10000;
			uint32_t n2 = r1 / 10000;
			uint32_t n3 = q1 % 10000;
			uint32_t r2 = q1 / 10000;
			uint32_t n4 = r2 % 10000;
			uint32_t q2 = r2 / 10000;
			uint32_t q3 = (q2 * 205) >> 11;
			uint32_t r3 = q2 - q3 * 10;
			memcpy(obuf + por + 14, pre.num + (n1 << 2), 4);
			memcpy(obuf + por + 10, pre.num + (n2 << 2), 4);
			memcpy(obuf + por + 6, pre.num + (n3 << 2), 4);
			memcpy(obuf + por + 2, pre.num + (n4 << 2), 4);
			obuf[por + 1] = '0' + r3;
			obuf[por + 0] = '0' + q3;
			por += 18;
		} else {
			uint32_t n1 = r1 % 10000;
			uint32_t n2 = r1 / 10000;
			uint32_t n3 = static_cast<uint32_t>(q1) % 10000;
			uint32_t r2 = static_cast<uint32_t>(q1) / 10000;
			uint32_t n4 = r2 % 10000;
			uint32_t q2 = r2 / 10000;
			memcpy(obuf + por + 13, pre.num + (n1 << 2), 4);
			memcpy(obuf + por + 9, pre.num + (n2 << 2), 4);
			memcpy(obuf + por + 5, pre.num + (n3 << 2), 4);
			memcpy(obuf + por + 1, pre.num + (n4 << 2), 4);
			obuf[por + 0] = '0' + q2;
			por += 17;
		}
	} else {
		int i = 8;
		char buf[12];
		while (x >= 10000) {
			memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
			x /= 10000;
			i -= 4;
		}
		if (x < 100) {
			if (x < 10) {
				wt(char('0' + x));
			} else {
				obuf[por + 0] = '0' + x / 10;
				obuf[por + 1] = '0' + x % 10;
				por += 2;
			}
		} else {
			if (x < 1000) {
				memcpy(obuf + por, pre.num + (x << 2) + 1, 3);
				por += 3;
			} else {
				memcpy(obuf + por, pre.num + (x << 2), 4);
				por += 4;
			}
		}
		memcpy(obuf + por, buf + i + 4, 8 - i);
		por += 8 - i;
	}
}

struct Dummy {
	Dummy() { atexit(flush); }
} dummy;

} // namespace fastio

using fastio::rd;
using fastio::wt;
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);
	rd(n);
	for (int i = 0; i < n; i++)
		rd(a[i]);
	for (int i = 1; i <= n; i++) {
		rd(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;
		rd(u);
		rd(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;
		}
	}
	wt(ans);
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 37248 KB Output is correct
2 Correct 22 ms 37312 KB Output is correct
3 Correct 24 ms 37276 KB Output is correct
4 Correct 22 ms 37316 KB Output is correct
5 Correct 20 ms 36408 KB Output is correct
6 Correct 19 ms 36300 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 127884 KB Output is correct
2 Correct 138 ms 127248 KB Output is correct
3 Correct 136 ms 128008 KB Output is correct
4 Correct 136 ms 128020 KB Output is correct
5 Correct 159 ms 127948 KB Output is correct
6 Correct 119 ms 71628 KB Output is correct
7 Correct 122 ms 72144 KB Output is correct
8 Correct 117 ms 72944 KB Output is correct
9 Correct 149 ms 74872 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35580 KB Output is correct
2 Correct 19 ms 35520 KB Output is correct
3 Correct 20 ms 35596 KB Output is correct
4 Correct 21 ms 35548 KB Output is correct
5 Correct 19 ms 35496 KB Output is correct
6 Correct 20 ms 35540 KB Output is correct
7 Correct 18 ms 35480 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 37248 KB Output is correct
2 Correct 22 ms 37312 KB Output is correct
3 Correct 24 ms 37276 KB Output is correct
4 Correct 22 ms 37316 KB Output is correct
5 Correct 20 ms 36408 KB Output is correct
6 Correct 19 ms 36300 KB Output is correct
7 Correct 21 ms 35580 KB Output is correct
8 Correct 19 ms 35520 KB Output is correct
9 Correct 20 ms 35596 KB Output is correct
10 Correct 21 ms 35548 KB Output is correct
11 Correct 19 ms 35496 KB Output is correct
12 Correct 20 ms 35540 KB Output is correct
13 Correct 18 ms 35480 KB Output is correct
14 Correct 22 ms 36308 KB Output is correct
15 Correct 25 ms 36240 KB Output is correct
16 Correct 23 ms 36264 KB Output is correct
17 Correct 24 ms 36228 KB Output is correct
18 Correct 24 ms 36316 KB Output is correct
19 Correct 22 ms 36344 KB Output is correct
20 Correct 24 ms 36432 KB Output is correct
21 Correct 21 ms 36440 KB Output is correct
22 Correct 22 ms 36436 KB Output is correct
23 Correct 22 ms 36444 KB Output is correct
24 Correct 23 ms 36572 KB Output is correct
25 Correct 23 ms 36484 KB Output is correct
26 Correct 24 ms 36580 KB Output is correct
27 Correct 29 ms 36652 KB Output is correct

Subtask #5
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 37248 KB Output is correct
2 Correct 22 ms 37312 KB Output is correct
3 Correct 24 ms 37276 KB Output is correct
4 Correct 22 ms 37316 KB Output is correct
5 Correct 20 ms 36408 KB Output is correct
6 Correct 19 ms 36300 KB Output is correct
7 Correct 149 ms 127884 KB Output is correct
8 Correct 138 ms 127248 KB Output is correct
9 Correct 136 ms 128008 KB Output is correct
10 Correct 136 ms 128020 KB Output is correct
11 Correct 159 ms 127948 KB Output is correct
12 Correct 119 ms 71628 KB Output is correct
13 Correct 122 ms 72144 KB Output is correct
14 Correct 117 ms 72944 KB Output is correct
15 Correct 149 ms 74872 KB Output is correct
16 Correct 21 ms 35580 KB Output is correct
17 Correct 19 ms 35520 KB Output is correct
18 Correct 20 ms 35596 KB Output is correct
19 Correct 21 ms 35548 KB Output is correct
20 Correct 19 ms 35496 KB Output is correct
21 Correct 20 ms 35540 KB Output is correct
22 Correct 18 ms 35480 KB Output is correct
23 Correct 22 ms 36308 KB Output is correct
24 Correct 25 ms 36240 KB Output is correct
25 Correct 23 ms 36264 KB Output is correct
26 Correct 24 ms 36228 KB Output is correct
27 Correct 24 ms 36316 KB Output is correct
28 Correct 22 ms 36344 KB Output is correct
29 Correct 24 ms 36432 KB Output is correct
30 Correct 21 ms 36440 KB Output is correct
31 Correct 22 ms 36436 KB Output is correct
32 Correct 22 ms 36444 KB Output is correct
33 Correct 23 ms 36572 KB Output is correct
34 Correct 23 ms 36484 KB Output is correct
35 Correct 24 ms 36580 KB Output is correct
36 Correct 29 ms 36652 KB Output is correct
37 Correct 324 ms 71884 KB Output is correct
38 Correct 281 ms 63884 KB Output is correct
39 Correct 333 ms 62600 KB Output is correct
40 Correct 312 ms 62544 KB Output is correct
41 Correct 341 ms 69868 KB Output is correct
42 Correct 352 ms 68696 KB Output is correct
43 Correct 307 ms 69180 KB Output is correct
44 Correct 289 ms 71348 KB Output is correct
45 Correct 330 ms 74668 KB Output is correct
46 Correct 276 ms 74648 KB Output is correct
47 Correct 275 ms 75452 KB Output is correct
48 Correct 297 ms 75772 KB Output is correct
49 Correct 326 ms 75672 KB Output is correct
50 Execution timed out 1559 ms 70872 KB Time limit exceeded
51 Halted 0 ms 0 KB -