oj.uz

Submission #791840

# Submission time Handle Problem Language Result Execution time Memory
791840 2023-07-24T10:52:39 Z 박영우(#10050) Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 467 ms 524288 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXS 500
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX] = { -1000000000 };
ll F[MAX];
int N;
namespace segtree {
	int N;
	ll tree[MAX];
	ll arr[MAX];
	void init(int s, int e, int loc = 1) {
		if (s == e) {
			arr[s] = F[s];
			tree[loc] = F[s];
			return;
		}
		int m = s + e >> 1;
		init(s, m, loc * 2);
		init(m + 1, e, loc * 2 + 1);
		tree[loc] = min(tree[loc * 2], tree[loc * 2 + 1]);
	}
	void upd(int s, int e, int i, ll x, int loc = 1) {
		if (e < i || i < s) return;
		if (s == e) {
			tree[loc] += x;
			return;
		}
		int m = s + e >> 1;
		upd(s, m, i, x, loc * 2);
		upd(m + 1, e, i, x, loc * 2 + 1);
		tree[loc] = min(tree[loc * 2], tree[loc * 2 + 1]);
	}
	void upd(int i, ll x) { upd(1, N, i, x); arr[i] += x; }
	ll query(int s, int e, int l, int r, int loc = 1) {
		if (e < l || r < s) return 1e18;
		if (l <= s && e <= r) return tree[loc];
		int m = s + e >> 1;
		return min(query(s, m, l, r, loc * 2), query(m + 1, e, l, r, loc * 2 + 1));
	}
	ll query(int l, int r) { return query(1, N, l, r); }
};
vector<int> adj[MAX];
ll ans[MAX];
ll aans[MAX]; // x=a, v=0
vector<pll> st[MAX];
ll all[MAX];
int dep[MAX];
int num[MAX];
void dfs(int x, int p = 0) { num[x] = 1; for (auto v : adj[x]) if (v != p) dep[v] = dep[x] + 1, dfs(v, x), num[x] += num[v]; }
int vis[MAX];
void calc(int x, int p = 0) {
	vis[x] = 1;
	int i;
	int ptr = 0;
	for (i = 0; i < adj[x].size(); i++) {
		int v = adj[x][i];
		if (dep[v] < dep[x]) continue;
		int c = 0;
		if (!A[v]) c = 1;
		else if (A[v] == A[x] + 1) c = 1;
		if (c) adj[x][ptr++] = adj[x][i];
	}
	adj[x].resize(ptr);
	sort(adj[x].begin(), adj[x].end(), [&](int i, int j) {return num[i] < num[j]; });
	int pv = 0;
	for (auto v : adj[x]) {
		if (pv) { for (auto& [a, b] : st[pv]) segtree::upd(a, -b); }
		calc(v, x);
		pv = v;
	}
	if (pv) {
		if (!A[pv]) {
			for (auto& [a, b] : st[pv]) segtree::upd(a, -b);
			st[pv].clear();
			all[pv] = ans[pv];
			st[pv].emplace_back(A[x] + 1, -ans[pv] + aans[pv]);
			segtree::upd(A[x] + 1, -ans[pv] + aans[pv]);
		}
		else {
			st[pv].emplace_back(A[pv], ans[pv] - all[pv]);
			segtree::upd(A[pv], ans[pv] - all[pv]);
		}
		all[x] += all[pv];
		swap(st[x], st[pv]);
		for (auto v : adj[x]) if (v != pv) {
			if (!A[v]) {
				all[x] += ans[v];
				st[x].emplace_back(A[x] + 1, -ans[v] + aans[v]);
				segtree::upd(A[x] + 1, -ans[v] + aans[v]);
			}
			else {
				all[x] += all[v];
				st[v].emplace_back(A[v], ans[v] - all[v]);
				for (auto& [a, b] : st[v]) st[x].emplace_back(a, b), segtree::upd(a, b);
			}
		}
	}
	ans[x] = all[x] + segtree::query(A[x] + 1, N);
	if (!A[x] && p) aans[x] = all[x] + segtree::arr[A[p] + 1] - F[A[p] + 1];
	if (!p) {
		for (auto& [a, b] : st[x]) segtree::upd(a, -b);
	}
}
ll dp[5050][5050];
ll get(int x, int k, int p = 0) {
	if (~dp[x][k]) return dp[x][k];
	ll sum = 0;
	for (auto v : adj[x]) if (v != p) {
		if (A[v] != (A[x] + 1) % k) sum += ans[v];
		else sum += min(ans[v], get(v, k, x));
	}
	return dp[x][k] = sum;
}
void naive(int x, int p = 0) {
	int i;
	ll mn = 1e18;
	for (auto v : adj[x]) if (v != p) naive(v, x);
	for (i = A[x] + 1; i <= N; i++) mn = min(mn, F[i] + get(x, i, p));
	ans[x] = mn;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N;
	segtree::N = N;
	int i, a, b;
	memset(dp, -1, sizeof(dp));
	for (i = 1; i <= N; i++) cin >> A[i];
	for (i = 1; i <= N; i++) cin >> F[i];
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	/*
	for (i = 1; i <= N; i++) A[i] = rand() % N;
	for (i = 1; i <= N; i++) F[i] = rand() % 1000000;
	for (i = 1; i < N; i++) {
		a = i;
		b = i + 1;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	*/
	naive(1);
	cout << ans[1] << ln;
	return 0;
	segtree::init(1, N);
	dfs(1);
	ll sum = 0;
	vector<int> v;
	for (i = 1; i <= N; i++) v.push_back(i);
	sort(v.begin(), v.end(), [&](int i, int j) {return dep[i] < dep[j]; });
	for (auto x : v) if (!vis[x]) {
		calc(x), sum += ans[x];
		//segtree::init(1, N);
	}
	for (i = 1; i <= N; i++) assert(segtree::arr[i] == F[i]);
	cout << sum << ln;
}

Compilation message

code1.cpp: In function 'void segtree::init(int, int, int)':
code1.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int m = s + e >> 1;
      |           ~~^~~
code1.cpp: In function 'void segtree::upd(int, int, int, ll, int)':
code1.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int m = s + e >> 1;
      |           ~~^~~
code1.cpp: In function 'll segtree::query(int, int, int, int, int)':
code1.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m = s + e >> 1;
      |           ~~^~~
code1.cpp: In function 'void calc(int, int)':
code1.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (i = 0; i < adj[x].size(); i++) {
      |              ~~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 248176 KB Output is correct
2 Correct 250 ms 248056 KB Output is correct
3 Correct 255 ms 248140 KB Output is correct
4 Correct 237 ms 248032 KB Output is correct
5 Correct 240 ms 247960 KB Output is correct
6 Correct 265 ms 248128 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 467 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 247348 KB Output is correct
2 Correct 135 ms 247368 KB Output is correct
3 Correct 96 ms 247336 KB Output is correct
4 Correct 94 ms 247324 KB Output is correct
5 Correct 103 ms 247396 KB Output is correct
6 Correct 100 ms 247328 KB Output is correct
7 Correct 92 ms 247364 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 248176 KB Output is correct
2 Correct 250 ms 248056 KB Output is correct
3 Correct 255 ms 248140 KB Output is correct
4 Correct 237 ms 248032 KB Output is correct
5 Correct 240 ms 247960 KB Output is correct
6 Correct 265 ms 248128 KB Output is correct
7 Correct 111 ms 247348 KB Output is correct
8 Correct 135 ms 247368 KB Output is correct
9 Correct 96 ms 247336 KB Output is correct
10 Correct 94 ms 247324 KB Output is correct
11 Correct 103 ms 247396 KB Output is correct
12 Correct 100 ms 247328 KB Output is correct
13 Correct 92 ms 247364 KB Output is correct
14 Correct 277 ms 247780 KB Output is correct
15 Correct 276 ms 247788 KB Output is correct
16 Correct 285 ms 247784 KB Output is correct
17 Correct 289 ms 247784 KB Output is correct
18 Correct 283 ms 247796 KB Output is correct
19 Correct 277 ms 247880 KB Output is correct
20 Correct 294 ms 247776 KB Output is correct
21 Correct 274 ms 247788 KB Output is correct
22 Correct 276 ms 247824 KB Output is correct
23 Correct 281 ms 247784 KB Output is correct
24 Correct 260 ms 247708 KB Output is correct
25 Correct 254 ms 247824 KB Output is correct
26 Correct 258 ms 247760 KB Output is correct
27 Correct 269 ms 247852 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 248176 KB Output is correct
2 Correct 250 ms 248056 KB Output is correct
3 Correct 255 ms 248140 KB Output is correct
4 Correct 237 ms 248032 KB Output is correct
5 Correct 240 ms 247960 KB Output is correct
6 Correct 265 ms 248128 KB Output is correct
7 Runtime error 467 ms 524288 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -