oj.uz

Submission #791838

# Submission time Handle Problem Language Result Execution time Memory
791838 2023-07-24T10:50:25 Z 박영우(#10050) Nestabilnost (COI23_nestabilnost) C++17
12 / 100
 410 ms 308396 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];
ll lim[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]) {
					b = min(lim[v], b);
					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);
	}
	lim[x] = ans[x] - all[x];
}
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:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (i = 0; i < adj[x].size(); i++) {
      |              ~~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49492 KB Output is correct
2 Correct 32 ms 49576 KB Output is correct
3 Correct 28 ms 49492 KB Output is correct
4 Correct 27 ms 49484 KB Output is correct
5 Correct 27 ms 48596 KB Output is correct
6 Correct 27 ms 48596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 151128 KB Output is correct
2 Runtime error 410 ms 308396 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 30 ms 47828 KB Output is correct
3 Correct 25 ms 47828 KB Output is correct
4 Correct 29 ms 47828 KB Output is correct
5 Correct 28 ms 47820 KB Output is correct
6 Correct 25 ms 47816 KB Output is correct
7 Incorrect 25 ms 47828 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49492 KB Output is correct
2 Correct 32 ms 49576 KB Output is correct
3 Correct 28 ms 49492 KB Output is correct
4 Correct 27 ms 49484 KB Output is correct
5 Correct 27 ms 48596 KB Output is correct
6 Correct 27 ms 48596 KB Output is correct
7 Correct 26 ms 47828 KB Output is correct
8 Correct 30 ms 47828 KB Output is correct
9 Correct 25 ms 47828 KB Output is correct
10 Correct 29 ms 47828 KB Output is correct
11 Correct 28 ms 47820 KB Output is correct
12 Correct 25 ms 47816 KB Output is correct
13 Incorrect 25 ms 47828 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49492 KB Output is correct
2 Correct 32 ms 49576 KB Output is correct
3 Correct 28 ms 49492 KB Output is correct
4 Correct 27 ms 49484 KB Output is correct
5 Correct 27 ms 48596 KB Output is correct
6 Correct 27 ms 48596 KB Output is correct
7 Correct 240 ms 151128 KB Output is correct
8 Runtime error 410 ms 308396 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -