Submission #832286

#	Time	Username	Problem	Language	Result	Execution time	Memory
832286		patrikpavic2	Nestabilnost (COI23_nestabilnost)	C++17	100 / 100	539 ms	199304 KiB

code1

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef long long ll;
typedef pair < ll, ll > pii;
typedef vector < pii > vp;

const int N = 3e5 + 50;
const ll INF = (ll)1e18;

int n, cst[N], a[N], naj[N], tko[N], min_cst[N], pos = 0;
vector < int > v[N];
ll dp_nula[N], off[N];
vector < ll > dp_am[N], dp_od[N];
set < pii > miin[N];
set < pii > govna[N];

inline ll get_dp(int v, int k) {
	if(a[v] >= k) return dp_nula[v];
	return dp_am[v][max(0, (int)dp_am[v].size() - (k - a[v]))] + off[v];	
}

void minaj(ll &x, ll y) {
	x = min(x, y);
}

void ocisti_od_sranja(int v, int dokle) {
	if(miin[v].size() == 0) return;
	int j = a[v] + 1; ll dos = INF;
	for(auto it = miin[v].begin();it != miin[v].end() && it -> X <= dokle;) {
		while(j < it -> X) {
			minaj(dp_am[v][(int)dp_am[v].size() - (j - a[v] - 1) - 1], dos);
			j++;
		}
		dos = min(dos, it -> Y);
		it = miin[v].erase(it);
		govna[v].erase({it -> Y + min_cst[it -> X], it -> X});
		
	}
	if(dokle < a[v] + (int)dp_am[v].size()) {
		miin[v].insert({dokle + 1, dos});
		govna[v].insert({dos + min_cst[dokle + 1], dokle + 1});
	}
	while(j <= dokle) minaj(dp_am[v][(int)dp_am[v].size() - (j - a[v] - 1) - 1], dos), j++;
	for(int j = a[v] + dp_am[v].size() - dokle;j < (int)dp_am[v].size();j++) {
		dp_od[v][j] = dp_am[v][j] + cst[a[v] + (int)dp_am[v].size() - j];
		if(j) dp_od[v][j] = min(dp_od[v][j], dp_od[v][j - 1]);
	}
}

void f(int x, int lst) {
	for(int y : v[x]) if(y != lst) f(y, x);
	if(tko[x] != -1) {
		swap(dp_am[x], dp_am[tko[x]]);
		swap(dp_od[x], dp_od[tko[x]]);
		swap(miin[x], miin[tko[x]]);
		swap(govna[x], govna[tko[x]]);
		off[x] = off[tko[x]];
		dp_am[x].PB(dp_nula[tko[x]] - off[x]);
		dp_od[x].PB(min(dp_od[x].back(), dp_am[x].back() + cst[a[x] + 1]));
	} else {
		off[x] = 0;
		dp_am[x] = {0, 0};
		dp_od[x] = {cst[a[x] + 2], min(cst[a[x] + 2], cst[a[x] + 1])};
	}
	for(int y : v[x]) {
		if(y == lst || y == tko[x]) continue;
		if(a[y] != a[x] + 1) {
			off[x] += dp_nula[y];
			if(!a[y]) { 
				dp_am[x].back() += min(0LL, get_dp(y, a[x] + 1) - dp_nula[y]);
				dp_od[x].back() = min(dp_am[x].back() + cst[a[x] + 1], dp_od[x][(int)dp_od[x].size() - 2]);
			}
		} else {
			ocisti_od_sranja(y, a[y] + dp_am[y].size());
			ocisti_od_sranja(x, a[y] + dp_am[y].size());
			ll y_poc = get_dp(y, a[y] + dp_am[y].size());
			off[x] += y_poc;
			for(int k = 0;k < (int)dp_am[y].size();k++) {
				dp_am[x][(int)dp_am[x].size() - k - 2] += get_dp(y, a[y] + k + 1) - y_poc;
			}
			dp_am[x].back() += dp_nula[y] - y_poc;
			for(int k = (int)dp_am[y].size(); k >= 0; k--) {
				int ind_x = (int)dp_am[x].size() - k - 1;
				dp_od[x][ind_x] = dp_am[x][ind_x] + cst[a[x] + k + 1];
				if(ind_x) dp_od[x][ind_x] = min(dp_od[x][ind_x], dp_od[x][ind_x - 1]);
			}
		}
	}
	dp_nula[x] = dp_od[x].back() + off[x];
	dp_nula[x] = min(dp_nula[x], off[x] + dp_am[x][0] + min_cst[a[x] + dp_am[x].size()]);
	if((int)govna[x].size() > 0)
		dp_nula[x] = min(dp_nula[x], off[x] + govna[x].begin()->X);
	miin[x].insert({a[x] + 2, dp_nula[x] - off[x]});
	govna[x].insert({dp_nula[x] - off[x] + min_cst[a[x] + 2], a[x] + 2});
	dp_am[x].back() = min(dp_am[x].back(), dp_nula[x] - off[x]);
	dp_od[x].back() = min(dp_od[x][(int)dp_od[x].size() - 2], dp_am[x].back() + cst[a[x] + 1]);
}

void dfs_priprema(int x, int lst) {
	tko[x] = -1; naj[x] = 2; pos++;
	for(int y : v[x]) {
		if(y == lst) continue;
		dfs_priprema(y, x);
		if(a[y] == a[x] + 1) {
			if(tko[x] == -1 || naj[y] > naj[tko[x]]) {
				naj[x] = naj[y] + 1; tko[x] = y;
			}
		}
	}
}


int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) scanf("%d", a + i);
	for(int i = 1;i <= n;i++) scanf("%d", cst + i);
	cst[n + 1] = cst[n]; min_cst[n + 1] = cst[n + 1];
	min_cst[n] = cst[n];
	for(int i = n - 1;i >= 1;i--) min_cst[i] = min(cst[i], min_cst[i + 1]);
	for(int i = 1;i < n;i++) {
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	dfs_priprema(1, 1);
	if(pos != n) return 0;
	f(1, 1);
	printf("%lld\n", dp_nula[1]);
	return 0;
}

Compilation message (stderr)

code1.cpp: In function 'int main()':
code1.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
code1.cpp:125:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  for(int i = 1;i <= n;i++) scanf("%d", a + i);
      |                            ~~~~~^~~~~~~~~~~~~
code1.cpp:126:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  for(int i = 1;i <= n;i++) scanf("%d", cst + i);
      |                            ~~~~~^~~~~~~~~~~~~~~
code1.cpp:131:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 20 / 20
• Subtask 3: 7 / 7
• Subtask 4: 22 / 22
• Subtask 5: 39 / 39