oj.uz

Submission #791825

# Submission time Handle Problem Language Result Execution time Memory
791825 2023-07-24T10:38:50 Z 박영우(#10050) Nestabilnost (COI23_nestabilnost) C++17
12 / 100
 403 ms 295636 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, min(0ll, -ans[pv] + aans[pv]));
			segtree::upd(A[x] + 1, min(0ll, -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, min(0ll, -ans[v] + aans[v]));
				segtree::upd(A[x] + 1, min(0ll, -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) {
	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 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;
	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);
	}
	*/
	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 23 ms 49364 KB Output is correct
2 Correct 22 ms 49392 KB Output is correct
3 Correct 24 ms 49376 KB Output is correct
4 Correct 29 ms 49444 KB Output is correct
5 Correct 23 ms 48536 KB Output is correct
6 Correct 23 ms 48596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 144628 KB Output is correct
2 Runtime error 403 ms 295636 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47828 KB Output is correct
2 Correct 29 ms 47776 KB Output is correct
3 Correct 26 ms 47792 KB Output is correct
4 Correct 27 ms 47824 KB Output is correct
5 Correct 26 ms 47828 KB Output is correct
6 Correct 27 ms 47848 KB Output is correct
7 Incorrect 30 ms 47824 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49364 KB Output is correct
2 Correct 22 ms 49392 KB Output is correct
3 Correct 24 ms 49376 KB Output is correct
4 Correct 29 ms 49444 KB Output is correct
5 Correct 23 ms 48536 KB Output is correct
6 Correct 23 ms 48596 KB Output is correct
7 Correct 26 ms 47828 KB Output is correct
8 Correct 29 ms 47776 KB Output is correct
9 Correct 26 ms 47792 KB Output is correct
10 Correct 27 ms 47824 KB Output is correct
11 Correct 26 ms 47828 KB Output is correct
12 Correct 27 ms 47848 KB Output is correct
13 Incorrect 30 ms 47824 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49364 KB Output is correct
2 Correct 22 ms 49392 KB Output is correct
3 Correct 24 ms 49376 KB Output is correct
4 Correct 29 ms 49444 KB Output is correct
5 Correct 23 ms 48536 KB Output is correct
6 Correct 23 ms 48596 KB Output is correct
7 Correct 271 ms 144628 KB Output is correct
8 Runtime error 403 ms 295636 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -