Submission #537401

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
537401	2022-03-15T04:57:54 Z	mmonteiro	Burza (COCI16_burza)	C++17	Compilation error	0 ms	0 KB

burza

#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;

#ifdef DEBUGMONTEIRO
#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;
#else
#define bug(x)
#endif

// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAX = 800; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, k;
vector<int> G[MAX];
int tin[MAX], tout[MAX], level[MAX], timer;
vector<int> bucket[MAX];
int dp[1 << 21][MAX];

void dfs(int v, int p) {
	if(level[v] >= 0)
		bucket[level[v]].push_back(v);

	tin[v] = timer + 1;
	for(int u : G[v]) {
		if(u != p) {
			level[u] = level[v] + 1;
			if(level[u] < k) {
				dfs(u, v);
			}
		}
	}
	if(level[v] == k - 1)	
		timer++;

	tout[v] = timer;
}

void solve() {
	cin >> n >> k;
	for(int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v; --u; --v;
		G[u].push_back(v);
		G[v].push_back(u);
	}

	level[0] = -1;
	dfs(0, -1);

	for(int i = 0; i <= k; ++i)
		sort(bucket[i].begin(), bucket[i].end(), [&](int a, int b)
			{
				return tin[a] < tin[b];
			}
		);

	for(int i = 0; i < (1 << k); ++i)
		dp[i][0] = 1;

	for(int i = 1; i < (1 << k); ++i) 
		for(int j = 0; j < k; ++j) 
			if(i & (1 << j)) 
				for(int u : bucket[j]) 
					if(dp[i ^ (1 << j)][ tin[u] - 1])
						dp[i][ tout[u] ] = 1;		

	bool flag = false;
	for(int i = 0; i < (1 << k); ++i)
		if(dp[i][timer])
			flag = true;

	cout << (flag ? "DA\n" : "NE\n");
}

int32_t main() {

	fastio;
	int t = 1;
	//cin >> t;
	for(int caso = 1; caso <= t; ++caso) {
		//cout << "Case #" << caso << ": ";
		solve();
	}

	return 0;
}

/*
Before submit:
	Check the corners cases
	Check solution restrictions

For implementation solutions:
	Check the flow of the variables

For intervals problems:
	Think about two pointers

For complete search:
	Think about cuts

If you get WA:
	Reread your code looking for stupid typos
	Try various manual testcases 
	Recheck the correctness of your algorithm
	Reread the statement
	Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
	Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
	Change the coder (if you're with a team)
	Give up. You may have other tasks to solve.
*/

Compilation message

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status