oj.uz

Submission #328088

# Submission time Handle Problem Language Result Execution time Memory
328088 2020-11-15T11:00:46 Z model_code Svjetlo (COCI20_svjetlo) C++17
110 / 110
 479 ms 90368 KB 
#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for(int i = 0; i < (n); i++)

const int maxn = 5e5 + 100;
const int inf = 1e9;

int n;

string poc_stanje;
vector <vector <int> > graf;

int dp[maxn][2][2];

void precalc(int cvor, int rod) {
	int suma = 0;
	bool parnost = poc_stanje[cvor] == '0';
	for(int dijete : graf[cvor]) {
		if(dijete == rod) continue;
		precalc(dijete, cvor);
		if(dp[dijete][0][0] != inf) suma += dp[dijete][0][0] + (dp[dijete][0][0] == 0 ? 0 : 3);
		else {
			suma += dp[dijete][0][1] + 1;
			parnost = !parnost;
		}
	}
	if(suma || poc_stanje[cvor] == '0') suma++;
	dp[cvor][0][parnost] = suma;
	return;
}

int rek(int cvor, int rod, int gore_vr, bool gore_par) {
	int ret = inf, suma;
	bool parnost;
	if(dp[cvor][0][0] != inf) parnost = 0;
	else parnost = 1;
	suma = dp[cvor][0][parnost];
	for(int dijete : graf[cvor]) {
		if(dijete == rod) continue;
		int nova_suma = suma;
		bool nova_parnost = parnost;
		if(dp[dijete][0][0] != inf) nova_suma -= dp[dijete][0][0] + (dp[dijete][0][0] == 0 ? 0 : 3);
		else {
			nova_suma -= dp[dijete][0][1] + 1;
			nova_parnost = !nova_parnost;
		}
		if(nova_suma == 1 && !nova_parnost) nova_suma = 0;
		int nova_gore_vr = nova_suma;
		if(!nova_gore_vr && gore_vr) nova_gore_vr = 1;
		nova_gore_vr += gore_vr;
		if(gore_par) nova_gore_vr += 1;
		else if(gore_vr) nova_gore_vr += 3;
		ret = min(ret, rek(dijete, cvor, nova_gore_vr, gore_par ^ nova_parnost));
		if(nova_parnost == 0) {
			if(nova_suma == 0) nova_suma = 1;
			dp[cvor][1][0] = min(dp[cvor][1][0], nova_suma + dp[dijete][1][1]);
			dp[cvor][1][1] = min(dp[cvor][1][1], nova_suma + dp[dijete][1][0] + 2);
		}
		else {
			dp[cvor][1][0] = min(dp[cvor][1][0], nova_suma + dp[dijete][1][0] + 2);
			dp[cvor][1][1] = min(dp[cvor][1][1], nova_suma + dp[dijete][1][1]);
		}
	}
	dp[cvor][1][parnost] = min(dp[cvor][1][parnost], max(1, dp[cvor][0][parnost]));
	if(gore_vr == 0) ret = min(ret, dp[cvor][1][1]);
	else if(gore_par) ret = min(ret, dp[cvor][1][0] + gore_vr + 1);
	else ret = min(ret, dp[cvor][1][1] + gore_vr + 3);
	bool uk_parnost = 0;
	if(dp[cvor][0][1] != inf) uk_parnost = 1;
	int uk_suma = dp[cvor][0][parnost];
	if(!uk_suma) uk_suma = 1;
	uk_suma += gore_vr;
	if(gore_par) {
		uk_parnost = !uk_parnost;
		uk_suma += 1;
	}
	else if(gore_vr) uk_suma += 3;
	int mini[2] = {inf, inf};
	for(int dijete : graf[cvor]) {
		if(dijete == rod) continue;
		bool dijete_parnost = 0;
		if(dp[dijete][0][1] != inf) dijete_parnost = 1;
		int prije = dp[dijete][0][dijete_parnost];
		if(dijete_parnost) prije += 1;
		else if(prije) prije += 3;
		int nova_suma = uk_suma - prije;
		bool nova_parnost = uk_parnost ^ dijete_parnost;
		ret = min(ret, dp[dijete][1][0] + 2 + nova_suma + mini[nova_parnost]);
		ret = min(ret, dp[dijete][1][1] + nova_suma + mini[!nova_parnost]);
		if(!dijete_parnost) {
			mini[0] = min(mini[0], dp[dijete][1][1] - prije);
			mini[1] = min(mini[1], dp[dijete][1][0] + 2 - prije);
		}
		else {
			mini[0] = min(mini[0], dp[dijete][1][0] + 2 - prije);
			mini[1] = min(mini[1], dp[dijete][1][1] - prije);
		}
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> n >> poc_stanje;
	REP(i, n) REP(j, 2) REP(k, 2) dp[i][j][k] = inf;
	graf.insert(graf.begin(), n, vector<int>());
	int a, b;
	REP(i, n - 1) {
		cin >> a >> b;
		a--; b--;
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
	precalc(0, -1);
	cout << rek(0, -1, 0, 0) << "\n";
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 51012 KB Output is correct
2 Correct 465 ms 80256 KB Output is correct
3 Correct 436 ms 90368 KB Output is correct
4 Correct 407 ms 60544 KB Output is correct
5 Correct 454 ms 71564 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 28160 KB Output is correct
2 Correct 479 ms 34672 KB Output is correct
3 Correct 433 ms 35904 KB Output is correct
4 Correct 319 ms 30208 KB Output is correct
5 Correct 334 ms 34432 KB Output is correct
6 Correct 277 ms 30976 KB Output is correct
7 Correct 334 ms 35316 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 315 ms 51012 KB Output is correct
11 Correct 465 ms 80256 KB Output is correct
12 Correct 436 ms 90368 KB Output is correct
13 Correct 407 ms 60544 KB Output is correct
14 Correct 454 ms 71564 KB Output is correct
15 Correct 373 ms 28160 KB Output is correct
16 Correct 479 ms 34672 KB Output is correct
17 Correct 433 ms 35904 KB Output is correct
18 Correct 319 ms 30208 KB Output is correct
19 Correct 334 ms 34432 KB Output is correct
20 Correct 277 ms 30976 KB Output is correct
21 Correct 334 ms 35316 KB Output is correct
22 Correct 412 ms 30848 KB Output is correct
23 Correct 445 ms 32696 KB Output is correct
24 Correct 430 ms 31360 KB Output is correct
25 Correct 365 ms 29952 KB Output is correct
26 Correct 352 ms 36864 KB Output is correct
27 Correct 362 ms 36608 KB Output is correct
28 Correct 287 ms 31744 KB Output is correct
29 Correct 324 ms 35328 KB Output is correct
30 Correct 299 ms 32624 KB Output is correct