oj.uz

Submission #398851

# Submission time Handle Problem Language Result Execution time Memory
398851 2021-05-04T21:27:00 Z AmineWeslati The Xana coup (BOI21_xanadu) C++14
10 / 100
 136 ms 20028 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define FOR(i,a,b) for(int i=a; i<b; i++)

void ckmin(int &x, int y){x=min(x,y);}

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
//------------------------------------------------//

const int MX=1e5+10;
const int INF=1e9;
int N; 
vi adj[MX],a(MX);

int cnt(int m){
	int ans=0;
	FOR(i,0,4) if((m>>i)&1) ans++;
	return ans; 
}

int memo[MX][2][2];
int solve(int u, int p, int f, int ff){
	int &ind=memo[u][f][ff];
	if(ind!=-1) return ind; 

	int st=a[u]; if(f) st=1-st; if(ff) st=1-st;

	int ans=INF,n=sz(adj[u])-(u!=1); 
	if(!n){
		if(!st) ans=ff;
		else ans=INF;
	} 
	else{
		FOR(m,0,(1)<<(n)) if(((cnt(m))&1)==st){

			int cur=ff,idx=0;
			for(int v: adj[u]) if(v!=p){
				int nf=(m>>idx)&1;
				idx++;
				cur+=solve(v,u,ff,nf);
			}

			ckmin(ans,cur);
		}
	}	
	return ind=ans; 

}

int main(){
	IO();

	cin>>N;
	FOR(i,0,N-1){
		int u,v; cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	FOR(i,1,N+1) cin>>a[i];
	//FOR(i,1,N+1) cout << a[i] << ' '; cout << endl;

	memset(memo,-1,sizeof(memo));
	/*int ans=solve(1,1,0,1);
	cout << ans << endl;*/
	int ans=min(solve(1,1,0,0),solve(1,1,0,1));
	if(ans==INF) cout << "impossible" << endl;
	else cout << ans << endl;

}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4556 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 136 ms 19832 KB Output is correct
2 Correct 125 ms 19700 KB Output is correct
3 Correct 129 ms 20004 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 19948 KB Output is correct
2 Correct 136 ms 19848 KB Output is correct
3 Correct 130 ms 20028 KB Output is correct
4 Incorrect 115 ms 8504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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