oj.uz

Submission #529634

# Submission time Handle Problem Language Result Execution time Memory
529634 2022-02-23T09:36:07 Z hohohaha From Hacks to Snitches (BOI21_watchmen) C++14
0 / 100
 275 ms 524292 KB 
#include<bits/stdc++.h> 
using namespace std; 

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++) 
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' ' 
#define endl '\n'
#define int long long

const int maxn = 2e5 + 5, inf = LLONG_MAX / 100ll; 
int n; 
vi g[maxn]; 
int ini[maxn]; 
int dp[maxn][2][2]; 
int nw[2][2]; 
void dfs(int u, int p ) { 
	dp[u][ini[u]][0] = 0;
	dp[u][ini[u] ^ 1][1] = 1; 
	for(int v: g[u]) { 
		if(v - p) { 
			dfs(v, u);
			fori(s, 0, 1) fori(var, 0, 1) nw[s][var] = inf; 
			fori(var, 0, 1) { 
				fori(s, 0, 1) { 
					fori(var_v, 0, 1) { 	
						nw[s ^ var_v][var] = min(nw[s ^ var_v][var], dp[u][s][var] + dp[v][var][var_v]);
					}
				}
			}
			fori(s, 0, 1) fori(var, 0, 1) dp[u][s][var] = nw[s][var]; 
		}
	}
//	fori(s, 0, 1) { 
//		fori(var, 0, 1) { 
//			cout << u << sp << s << sp << var << sp << dp[u][s][var] << endl; 
//		}
//	}
}
signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);  
	cin >> n; 
	fori(i, 1, n - 1) { 
		int u, v; 
		cin >> u >> v; 
		g[u].eb(v); g[v].eb(u); 
	}
	fori(i, 1, n) cin >> ini[i]; 
	fori(i, 1, n) { 
		fori(s, 0, 1) { 
			fori(var, 0, 1) { 
				dp[i][s][var] = inf; 
			}
		}
	}
	dfs(1, 1); 
	int ans = min(dp[1][0][0], dp[1][0][1]); 
	if(ans == inf) { 
		cout << "impossible" << endl; 
	}
	else cout << ans; 
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 275 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 275 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 275 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -