Submission #577222

#	Time	Username	Problem	Language	Result	Execution time	Memory
577222		GioChkhaidze	Burza (COCI16_burza)	C++14	160 / 160	21 ms	3020 KiB

burza

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;

const int N = 404;

bool f[N][527288];
int n, k, ts, depth, L[N], R[N];
vector < pair < int , int > > mv[N];
vector < int > v[N];

void dfs(int x, int p) {
	++depth;
	L[x] = 1e9, R[x] = -1e9;
	if (depth > k + 1) {
		--depth;
		return ;
	}
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to == p) continue;
		dfs(to, x);
		L[x] = min(L[x], L[to]);
		R[x] = max(R[x], R[to]);
	}
	if (depth == k + 1) {
		L[x] = R[x] = ++ts;
	}
	if (L[x] != 1e9 && x != p) {
		mv[L[x]].pb({R[x], depth - 2});
	}
	--depth;
}

int main() {
	cin >> n >> k;
	if (k * k >= n) {
		cout << "DA\n";
	}
		else {
		for (int i = 1; i < n; ++i) {
			int a, b;
			cin >> a >> b;
			v[a].pb(b);
			v[b].pb(a);
		}

		dfs(1, 1);
		f[0][0] = true;
		for (int i = 1; i <= ts; ++i) {
			for (int ms = 0; ms < (1 << k); ++ms) {
				if (!f[i - 1][ms]) continue;
				for (int j = 0; j < mv[i].size(); ++j) {
					int jmp = mv[i][j].f;
					int dep = mv[i][j].s;
					if ((ms >> dep) & 1) continue;
					f[jmp][(ms | (1 << dep))] = true;
				}
			}	
		}

		for (int ms = 0; ms < (1 << k); ++ms) {
			if (f[ts][ms]) {
				cout << "DA\n";
				exit(0);
			}
		}

		cout << "NE\n";
	}
}

Compilation message (stderr)

burza.cpp: In function 'void dfs(int, int)':
burza.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
burza.cpp: In function 'int main()':
burza.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int j = 0; j < mv[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~

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