oj.uz

Submission #487872

# Submission time Handle Problem Language Result Execution time Memory
487872 2021-11-16T20:56:40 Z cfalas The Xana coup (BOI21_xanadu) C++14
50 / 100
 132 ms 23364 KB 
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD ((ll)1000000007)
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

int t, n;
vi a, b;

vector<vi> adj;
ll dp[200000][2][2];
ll dfs(int s, int x, int xp, int p=0){
	if(dp[s][x][xp]!=-1) return dp[s][x][xp];
	ll ans=0;
	int c = a[s];
	if(xp) c = 1-c;
	if(x) c = 1-c, ans++;

	int ccnt=0;
	FOA(v, adj[s]) if(v!=p) ccnt++;

	if(ccnt==1){
		//cout<<s<<" "<<x<<" "<<xp<<" C 1\n";
		FOA(v, adj[s]){
			if(v!=p) ans+= dfs(v, c, x, s);
		}
	}
	else if(ccnt==2){
		ll a1=0, a2=0;
		int cnt=0;
		FOA(v, adj[s]){
			if(v==p) continue;
			a1+= dfs(v, cnt, x, s);
			a2+= dfs(v, 1-cnt, x, s);
			if(c) cnt = 1-cnt;
		}
		ans += min(a1, a2);

	}
	else if(ccnt==0 && c!=0) ans = MOD;
	dp[s][x][xp] = ans;
	//cout<<s<<" "<<x<<" "<<xp<<": "<<ans<<endl;
	return ans;
}

int main(){
	cin>>n;
	adj.assign(n+1, vi());
	FOR(i,n+2) dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = -1;
	FOR(i,n-1){
		int a, b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	a.resize(n+1);
	a[0] = 0;
	FOR(i,n){
		cin>>a[i+1];
	}
	int root=1;
	FOR(i,n) if(adj[i+1].size()<=2) root=i+1;
	ll ans1 = dfs(root, 0, 0);
	ll ans2 = dfs(root, 1, 0);
	if(ans1 >= MOD && ans2 >= MOD) cout<<"impossible\n";
	else cout<<min(ans1, ans2)<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 23176 KB Output is correct
2 Correct 113 ms 22984 KB Output is correct
3 Correct 119 ms 23308 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 23176 KB Output is correct
2 Correct 105 ms 22912 KB Output is correct
3 Correct 110 ms 23364 KB Output is correct
4 Correct 112 ms 8300 KB Output is correct
5 Correct 122 ms 9112 KB Output is correct
6 Correct 95 ms 9224 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 28 ms 3352 KB Output is correct
9 Correct 132 ms 9216 KB Output is correct
10 Correct 129 ms 9336 KB Output is correct
11 Correct 100 ms 10116 KB Output is correct
12 Correct 103 ms 11072 KB Output is correct
13 Correct 87 ms 8664 KB Output is correct
14 Correct 95 ms 9244 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -