Submission #795367

#	Time	Username	Problem	Language	Result	Execution time	Memory
795367		abhinavshukla408	Burza (COCI16_burza)	C++17	0 / 160	5 ms	4692 KiB

burza

#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<vector<int>> cutoff_cover;
vector<pii> intervals;
map<int,int> lost;
 
bool dfs(int a,int prev,int cur){
	if(cur>K){
		return true;
	}
	if(cur==K){
		cutoff_cover[a]={a};
		lost[a]=lost.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];
				cutoff_cover[a].insert(cutoff_cover[a].end(),cutoff_cover[i].begin(),cutoff_cover[i].end());
			}
		}
	}
	if(cur==K){
		//futLeaves[a]=(1<<a);
		
		depth[cur].pb(a);
		return true;
	}
	if(found){
		if(cur>=0){
			depth[cur].pb(a);
		}
	}
	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;
}
int max(int a, int b){
	if(a>b){
		return a;
	}
	return b;
}
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin>>N>>K;
	adj.resize(N);
	// futLeaves.resize(N+1);
	
	depth.resize(K+1);	
	cutoff_cover.resize(N);
	
	FOR0(i,N-1){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	assert(0==0);
	if ((K * K) >= N) {
		cout << "DA" << endl;
		return 0;
	}
	//cout<<"cp2"<<endl;
	//return 0;
	dfs(0,-1,-1);
	//return 0;
	// intervals.pb({-1,-1});
	TRAV(i,cutoff_cover){
		if(i.empty()){
			intervals.pb({-1,-1});
		}else{
			intervals.pb({lost[i[0]],lost[i.back()]});
		}
	}
	// FOR1(i,N){
	// 	cout<<i<<" : "<<toBinary(futLeaves[i],N)<<endl;
	// }
	// TRAV(i,leaves){
	// 	cout<<i.first<<" "<<i.second<<endl;
	// }
	int dp[1<<(K+1)];
	//cout<<"cp1"<<endl;
	//return 0;
	bool works=false;
	FOR0(i,1<<K){
		if(i==0){dp[i]=0; continue;}
		dp[i]=0;

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

Compilation message (stderr)

burza.cpp: In function 'std::string toBinary(int64_t, int64_t)':
burza.cpp:85:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   85 |     for (unsigned i = (1 << len - 1); i > 0; i = i / 2) {
      |                             ~~~~^~~
burza.cpp: In function 'int32_t main()':
burza.cpp:161: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]
  161 |   if(dp[i]==(depth[K].size()-1)){
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~
burza.cpp:142:7: warning: variable 'works' set but not used [-Wunused-but-set-variable]
  142 |  bool works=false;
      |       ^~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16