| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 379142 |
2021-03-17T10:27:30 Z |
kartel |
Svjetlo (COCI20_svjetlo) |
C++14 |
|
515 ms |
59520 KB |
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;
const int N = 5e5 + 500;
vector <int> g[N];
int f[N][2][2];
int a[N];
int n;
void dfs(int v, int pr) {
int cur = 0;
bool parity = (a[v] == 0);
for (auto u : g[v]) {
if (u == pr) {
continue;
}
dfs(u, v);
if (f[u][0][0] != 1e9) {
cur += f[u][0][0] + (f[u][0][0] == 0 ? 0 : 3);
}
else {
cur += f[u][0][1] + 1;
parity = !parity;
}
}
if (cur || !a[v]) {
cur++;
}
f[v][0][parity] = cur;
}
int calc(int v, int pr, int sum, bool par) {
int ret = 1e9, sumv;
bool parity = 0;
if (f[v][0][0] == 1e9) {
parity = 1;
}
sumv = f[v][0][parity];
for (auto u : g[v]) {
if (u == pr) {
continue;
}
int new_sumv = sumv;
bool new_parity = parity;
if (f[u][0][0] != 1e9) {
new_sumv -= f[u][0][0] + (f[u][0][0] == 0 ? 0 : 3);
}
else {
new_sumv -= f[u][0][1] + 1;
new_parity = !new_parity;
}
///if take one extra turn
if (!new_parity && new_sumv == 1) {
new_sumv = 0;
}
int new_sum = new_sumv;
if (!new_sum && sum) {
new_sum = 1;
}
new_sum += sum;
if (par) {
new_sum++;
}
else if (sum) {
new_sum += 3;
}
/// if primary path in subtree of vertex u
ret = min(ret, calc(u, v, new_sum, new_parity ^ par));
if (!new_parity) {
/// if didn't change parity
if (!new_sumv) {
new_sumv++;
}
f[v][1][0] = min(f[v][1][0], new_sumv + f[u][1][1]);
f[v][1][1] = min(f[v][1][1], new_sumv + f[u][1][0] + 2);
}
else {
f[v][1][0] = min(f[v][1][0], new_sumv + f[u][1][0] + 2);
f[v][1][1] = min(f[v][1][1], new_sumv + f[u][1][1]);
}
}
int mn[2]; mn[0] = mn[1] = 1e9;
f[v][1][parity] = min(f[v][1][parity], max(1, f[v][0][parity]));
/// if we haven't primary path in upper subtree and primary path go from vertex v to some vertex in subtree
if (!sum) {
///good upper subtree
ret = min(ret, f[v][1][1]);
}
else {
if (par) {
/// go down from upper subtree and change parity in vertex v
ret = min(ret, f[v][1][0] + sum + 1);
}
else {
///need change parity in parent
ret = min(ret, f[v][1][1] + sum + 3);
}
}
bool parity_now = (f[v][0][1] != 1e9) ? 1 : 0;
int sum_now = max(1, f[v][0][parity]);
sum_now += sum;
if (par) {
parity_now = !parity_now;
sum_now++;
}
else if (sum) {
sum_now += 3;
}
/// two children include in primary path
for (auto u : g[v]) {
if (u == pr){
continue;
}
bool c_parity = (f[u][0][1] != 1e9) ? 1 : 0;
int fu = f[u][0][c_parity];
if (c_parity) {
fu++;
}
else {
if (fu) {
fu += 3;
}
}
int new_sum = sum_now - fu;
bool new_parity = c_parity ^ parity_now;
/// change parity in child
ret = min(ret, f[u][1][0] + 2 + new_sum + mn[new_parity]);
/// without changing
ret = min(ret, f[u][1][1] + new_sum + mn[!new_parity]);
if (!c_parity) {
mn[0] = min(mn[0], f[u][1][1] - fu);
mn[1] = min(mn[1], f[u][1][0] + 2 - fu);
}
else {
mn[0] = min(mn[0], f[u][1][0] + 2 - fu);
mn[1] = min(mn[1], f[u][1][1] - fu);
}
}
return ret;
}
int main()
{
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("toys.in");
// out("toys.out");
// in("input.txt");
// out("output.txt");
// cerr.precision(9); cerr << fixed;
// clock_t tStart = clock();
cin >> n;
for (int i = 0; i < n; i++) {
char c;
cin >> c;
a[i] = c - '0';
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
f[i][j][k] = 1e9;
}
}
}
// calc if subtree will be good
dfs(1, -1);
cout << calc(1, -1, 0, 0) << el;
}
/*
7
4 6 7 2 3 1 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
328 ms |
59520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
35184 KB |
Output is correct |
| 2 |
Correct |
515 ms |
43500 KB |
Output is correct |
| 3 |
Correct |
459 ms |
44140 KB |
Output is correct |
| 4 |
Correct |
363 ms |
39148 KB |
Output is correct |
| 5 |
Correct |
388 ms |
43244 KB |
Output is correct |
| 6 |
Correct |
316 ms |
40172 KB |
Output is correct |
| 7 |
Correct |
375 ms |
44252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
