oj.uz

Submission #795340

# Submission time Handle Problem Language Result Execution time Memory
795340 2023-07-27T08:29:07 Z abhinavshukla408 Burza (COCI16_burza) C++17
0 / 160
 2 ms 1364 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<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;
}
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)];
	//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(first<=(dp[i & ~(1<<j)]+1)){
					// 	dp[i]=max(dp[i],last);
					// }
					
				}
			}
		}
		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;
	}
	
 
	
 
 
 
 
	return 0;
}

Compilation message

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:145:10: warning: unused variable 'first' [-Wunused-variable]
  145 |      int first=intervals[l].first;
      |          ^~~~~
burza.cpp:146:10: warning: unused variable 'last' [-Wunused-variable]
  146 |      int last=intervals[l].second;
      |          ^~~~
burza.cpp:155: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]
  155 |   if(dp[i]==(depth[K].size()-1)){
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 0 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 #2
0 / 16.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 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 1 ms 596 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 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 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 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 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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

Subtask #8
0 / 16.0

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

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 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 1 ms 852 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 852 KB Output isn't correct
6 Halted 0 ms 0 KB -