oj.uz

Submission #795185

# Submission time Handle Problem Language Result Execution time Memory
795185 2023-07-27T07:21:46 Z abhinavshukla408 Burza (COCI16_burza) C++17
0 / 160
 578 ms 2400 KB 
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
 
using namespace std;
 
#define endl "\n"
#define int int64_t 
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR0(i,a) FOR(i,0,a)
#define FOR1(i,a) for (int i = (1); i <= (a); ++i)
#define TRAV(a,x) for (auto& a: x)
 
using pii = pair<int,int>;
using vi = vector<int>;
 
void printBin(int n, int len){
	cout<<"(";
	bool prev=false;
	for(int i=0;i<=len;i++){
		if(n & (1<<i)){
			if(prev)
				cout<<",";
			cout<<i;
			prev=true;
		}
	}
	cout<<")";
}
 
int N,K;
vector<vector<int>> adj;
vector<vector<int>> depth;
vector<int> nodeDepth;
vector<int> futLeaves;
map<int,int> leaves;
 
bool dfs(int a,int prev,int cur){
	if(cur>K){
		return true;
	}
	if(cur==K){
		leaves[a]=leaves.size();
	}
	bool found=false;
	TRAV(i,adj[a]){
		if(i!=prev){
			bool val=dfs(i,a,cur+1);
			if(val){
				found=val;
				futLeaves[a]=futLeaves[a] | futLeaves[i];
				
			}
		}
	}
	if(cur==K){
		futLeaves[a]=(1<<a);
		nodeDepth[a]=cur;
		depth[cur].pb(a);
		return true;
	}
	if(found){
		depth[cur].pb(a);
		nodeDepth[a]=cur;
	}
	return found;
}
 
string toBinary(int n, int len)
{
    string binary;
    for (unsigned i = (1 << len - 1); i > 0; i = i / 2) {
        binary += (n & i) ? "1" : "0";
    }
 
    return binary;
}
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin>>N>>K;
	adj.resize(N+1);
	futLeaves.resize(N+1);
	nodeDepth.resize(N+1);
	depth.resize(K+1);
	FOR1(i,N){
		futLeaves[i]=0;
		nodeDepth[i]=-1;
	}
	FOR0(i,N-1){
		int a,b;
		cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	if (K * K >= N) {
		cout << "DA" << endl;
		return 0;
	}
	dfs(1,-1,0);
	
	// FOR1(i,N){
	// 	cout<<i<<" : "<<toBinary(futLeaves[i],N)<<endl;
	// }
	// TRAV(i,leaves){
	// 	cout<<i.first<<" "<<i.second<<endl;
	// }
	int dp[1<<(K+1)];

	bool works=false;
	FOR0(i,1<<(K)){
		dp[i]=0;
		if(i==1){
			dp[1]=0;
			continue;
		}
		FOR0(j,K+1){
			if(i & (1<<j)){
				TRAV(k,depth[j]){
					//cout<<"AB: "<<j<<" "<<k<<endl;
					int cur=futLeaves[k];
					//return 0;
					if(cur==0){continue;}
					int first=N+2;
					int last=-1;
					for(int h=0;h<=N;h++){
						if(cur & (1<<h)){
							//cout<<"in: "<<h<<"  "<<leaves[h]<<endl;
							first=min(leaves[h],first);
							break;
						}
					}
					for(int h=N;h>=0;h--){
						if(cur & (1<<h)){
							last=max(leaves[h],last);
							break;
						}
					}

					// TRAV(l,leaves){
					// 	if(l.second>=first && l.second<=last){
					// 		assert(cur & (1<<l.first));
					// 	}
					// }
					// assert(first!=(N+2));
					// assert(last!=(-1));
 
					int bef=i & ~(1<<j);
					if(first<=(dp[bef]+1)){
						dp[i]=max(dp[i],last);
					}
				//	return 0;
				}
			}
		}
		if(dp[i]==(depth[K].size()-1)){
			works=true;
		}
	}
	// FOR0(i,1<<(K)){
	// 	printBin(i,N);
	// 	cout<<" "<<dp[i]<<endl;
	// }
	if(works){
		cout<<"DA"<<endl;
	}else{
		cout<<"NE"<<endl;
	}
	
 
	
 
 
 
 
	return 0;
}

Compilation message

burza.cpp: In function 'std::string toBinary(int64_t, int64_t)':
burza.cpp:82:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   82 |     for (unsigned i = (1 << len - 1); i > 0; i = i / 2) {
      |                             ~~~~^~~
burza.cpp: In function 'int32_t main()':
burza.cpp:167:11: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |   if(dp[i]==(depth[K].size()-1)){
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 596 KB Output is correct
2 Correct 462 ms 2392 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 2392 KB Output is correct
2 Correct 459 ms 2396 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 494 ms 2392 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 2392 KB Output is correct
2 Correct 481 ms 2392 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 852 KB Output is correct
2 Correct 549 ms 2392 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 2388 KB Output is correct
2 Correct 527 ms 2396 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 2396 KB Output is correct
2 Correct 489 ms 2396 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 1 ms 316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 2400 KB Output is correct
2 Correct 479 ms 2396 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 566 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 852 KB Output is correct
2 Correct 517 ms 2400 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 596 KB Output is correct
2 Correct 561 ms 2400 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 1364 KB Output is correct
2 Correct 470 ms 2400 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 218 ms 1364 KB Output isn't correct
6 Halted 0 ms 0 KB -