| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 379463 |
2021-03-18T09:42:48 Z |
Vimmer |
Svjetlo (COCI20_svjetlo) |
C++14 |
|
464 ms |
79744 KB |
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define N 500505
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;
int f[N][2][2], ans = 1e9;
vector <int> g[N];
string s;
void rec(int v, int p)
{
int gd = !(s[v] == '1');
int sum = 1;
for (auto it : g[v])
{
if (it == p) continue;
rec(it, v);
if (f[it][1][0] == 0) continue;
if (f[it][1][0] != 1e9)
{
sum += f[it][1][0];
}
else
{
sum += f[it][0][0] + 2;
gd = !gd;
}
gd = !gd;
sum++;
}
if (sum == 1 && s[v] == '1')
{
f[v][1][0] = 0;
return;
}
f[v][gd][0] = sum;
}
void dfs(int v, int p, int skok, bool clr)
{
int sum = 1;
if (f[v][0][0] != 1e9)
f[v][0][1] = f[v][0][0];
else f[v][1][1] = f[v][1][0];
bool gd = !(s[v] == '1');
for (auto it : g[v])
{
if (it == p) continue;
if (f[it][1][0] == 0) continue;
if (f[it][1][0] != 0)
{
sum += f[it][1][0];
}
else
{
sum += f[it][0][0] + 2;
gd = !gd;
}
gd = !gd;
sum++;
}
int smr = f[v][1][0];
bool cl = 1;
if (smr == 1e9)
{
smr = f[v][0][0];
cl = 0;
}
for (auto it : g[v])
{
if (it == p) continue;
if (f[it][1][0] == 0) continue;
int cur = smr; /// start in v
bool c = cl;
cur--;
c = !c;
if (f[it][1][0] != 1e9)
{
cur -= f[it][1][0];
}
else
{
cur -= f[it][0][0] + 2;
c = !c;
}
cur += skok;
if (skok != 0)
{
c = !c;
cur++;
}
if (clr == 0)
{
c = !c;
cur += 2;
}
if (cur == 1 && c == 0)
{
c = 1;
cur--;
}
dfs(it, v, cur, c);
bool g = cl;
int sm = smr - 1; /// start
g = !g; /// start
if (f[it][1][0] != 1e9)
{
sm -= f[it][1][0];
}
else
{
sm -= f[it][0][0] + 2;
g = !g;
}
if (f[it][1][1] != 1e9)
{
sm += f[it][1][1];
f[v][g][1] = min(f[v][g][1], sm);
sm -= f[it][1][1];
}
if (f[it][0][1] != 1e9)
{
sm += f[it][0][1] + 2;
g = !g;
f[v][g][1] = min(f[v][g][1], sm);
}
}
/// when ends in v
{
if (f[v][1][1] != 1e9)
{
smr = f[v][1][1];
cl = 1;
if (skok != 0)
{
smr += skok;
smr++;
cl = !cl;
}
if (clr == 0)
{
smr += 2;
cl = !cl;
}
if (cl == 0 && smr == 0)
{
smr++;
cl = 1;
}
if (cl == 1)
ans = min(ans, smr);
}
if (f[v][0][1] != 1e9)
{
smr = f[v][0][1];
cl = 0;
if (skok != 0)
{
smr += skok;
smr++;
cl = !cl;
}
if (clr == 0)
{
smr += 2;
cl = !cl;
}
if (cl == 0 && smr == 0)
{
smr++;
cl = 1;
}
if (cl == 1)
ans = min(ans, smr);
}
}
/// when v is lca of x and y
{
int dp[2] = {int(1e9), int(1e9)}, pr[2] = {-1, -1};
for (auto it : g[v])
{
if (it == p) continue;
if (f[it][1][0] == 0) continue;
if (f[it][1][1] != 1e9 && dp[1] > f[it][1][1])
{
dp[1] = f[it][1][1];
pr[1] = it;
}
if (f[it][0][1] != 1e9 && dp[0] > f[it][0][1])
{
dp[0] = f[it][0][1];
pr[0] = it;
}
}
int smt[2];
bool color[2];
if (f[v][1][0] != 1e9)
{
smt[0] = smt[1] = f[v][1][0];
color[0] = color[1] = 1;
}
else
{
smt[0] = smt[1] = f[v][0][0];
color[0] = color[1] = 0;
}
if (dp[0] != 1e9)
{
int it = pr[0];
smt[0]--; /// start
color[0] = !color[0];
smt[0]--;
color[0] = !color[0];
if (f[it][1][0] != 1e9)
{
smt[0] -= f[it][1][0];
}
else
{
smt[0] -= f[it][0][0] + 2;
color[0] = !color[0];
}
}
if (dp[1] != 1e9)
{
int it = pr[1];
smt[1]--;
color[1] = !color[1];
smt[1]--; /// start
color[1] = !color[1];
if (f[it][1][0] != 1e9)
{
smt[1] -= f[it][1][0];
}
else
{
smt[1] -= f[it][0][0] + 2;
color[1] = !color[1];
}
}
for (auto it : g[v])
{
if (it == p) continue;
if (f[it][1][0] == 0) continue;
/// 0 1
if (dp[0] != 1e9 && pr[0] != it && f[it][1][1] != 1e9)
{
int sum = dp[0] + f[it][1][1] + 2 + smt[0] + 1;
/// for one 0
/// for one step throw
/// for maybe one step up
bool cur = color[0];
if (f[it][1][0] != 1e9)
{
sum -= f[it][1][0];
}
else
{
sum -= f[it][0][0] + 2;
cur = !cur;
}
sum--;
cur = !cur;
sum += skok;
if (skok != 0)
{
sum++;
cur = !cur;
}
if (clr == 0)
{
sum += 2;
cur = !cur;
}
if (cur == 1)
ans = min(ans, sum);
}
/// 1 1
if (dp[1] != 1e9 && pr[1] != it && f[it][1][1] != 1e9)
{
int sum = dp[1] + f[it][1][1] + 1 + smt[1];
/// for one step throw
/// for maybe one step up
bool cur = !color[1];
if (f[it][1][0] != 1e9)
{
sum -= f[it][1][0];
}
else
{
sum -= f[it][0][0] + 2;
cur = !cur;
}
sum--;
cur = !cur;
sum += skok;
if (skok != 0)
{
sum++;
cur = !cur;
}
if (clr == 0)
{
sum += 2;
cur = !cur;
}
if (cur == 1)
ans = min(ans, sum);
}
/// 1 0
if (dp[1] != 1e9 && pr[1] != it && f[it][0][1] != 1e9)
{
int sum = dp[1] + f[it][0][1] + 2 + 1 + smt[1];
/// for one 0
/// for one step throw
/// for maybe one step up
bool cur = color[1];
if (f[it][1][0] != 1e9)
{
sum -= f[it][1][0];
}
else
{
sum -= f[it][0][0] + 2;
cur = !cur;
}
sum--;
cur = !cur;
sum += skok;
if (skok != 0)
{
sum++;
cur = !cur;
}
if (clr == 0)
{
sum += 2;
cur = !cur;
}
if (cur == 1)
ans = min(ans, sum);
}
/// 0 0
if (dp[0] != 1e9 && pr[0] != it && f[it][0][1] != 1e9)
{
int sum = dp[0] + f[it][0][1] + 2 + 2 + 1 + smt[0];
/// for two 0
/// for one step throw
/// for maybe one step up
bool cur = !color[0];
if (f[it][1][0] != 1e9)
{
sum -= f[it][1][0];
}
else
{
sum -= f[it][0][0] + 2;
cur = !cur;
}
sum--;
cur = !cur;
sum += skok;
if (skok != 0)
{
sum++;
cur = !cur;
}
if (clr == 0)
{
sum += 2;
cur = !cur;
}
if (cur == 1)
ans = min(ans, sum);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
for (int i = 0; i < N; i++)
for (int t = 0; t < 2; t++)
for (int r = 0; r < 2; r++)
f[i][t][r] = 1e9;
int n;
cin >> n;
cin >> s;
for (int i = 1; i < n; i++)
{
int x, y;
cin >> x >> y;
x--; y--;
g[x].PB(y);
g[y].PB(x);
}
rec(0, -1);
dfs(0, -1, 0, 1);
pri(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
20076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
322 ms |
51968 KB |
Output is correct |
| 2 |
Correct |
461 ms |
71552 KB |
Output is correct |
| 3 |
Correct |
464 ms |
79744 KB |
Output is correct |
| 4 |
Correct |
396 ms |
57216 KB |
Output is correct |
| 5 |
Correct |
453 ms |
64768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
395 ms |
32768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
20076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
