Submission #701717

#	Time	Username	Problem	Language	Result	Execution time	Memory
701717		thomasqm	Burza (COCI16_burza)	C++17	160 / 160	917 ms	417372 KiB

burza

#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <list>
#include <array>
#include <set>
#include <map>
#include <chrono>
#include <stack>
#include <random>
#include <climits>
#include <algorithm>
#include <tgmath.h>

using namespace std;

int main() {
	int n,k; cin>>n>>k;
	vector<vector<unsigned>> adj(n);
	for (unsigned i=0; i<n-1; i++) {
		unsigned a,b; cin>>a>>b; a--, b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	if (k*k>=n) {
		cout<<"DA\n"; return 0;
	}

	vector<array<int, 2>> to((1<<k)*n);
	vector<int> parent(n, 0), next(n, 0), dist(n, 0);
	vector<bool> visited(n, false), good(n,false);

	stack<unsigned> dfs({0});
	while (dfs.size()) {
		unsigned x = dfs.top();

		if (!visited[x]) {
			for (unsigned a: adj[x]) {
				if (a!=parent[x]) {
					parent[a]=x;
					dist[a]=dist[x]+1;
					dfs.push(a);
				}
			}

			if (dist[x]>=k) good[x]=true;
			visited[x]=true;
			continue;
		} else if (!good[x]) {
			dfs.pop();
			continue;
		} else {
			good[parent[x]]=true;
			dfs.pop();
		}
	}

	dfs.push(0);

	vector<int> child;
	while (dfs.size()) {
		unsigned x = dfs.top(); dfs.pop();

		child.clear();
		for (unsigned a: adj[x]) {
			if (a!=parent[x] && good[a]) dfs.push(a), child.push_back(a);
		}
		
		for (unsigned i=0; i<child.size(); i++) {
			next[child[i]] = i+1==child.size() ? next[x] : child[i+1];
		}

		for (int i=0; i<(1<<k); i++) {
			to[i*n + x][1] = child.size() ? (i*n + child[0]) : -1;
			if (dist[x]>0 && dist[x]<=k && (i&(1<<(dist[x]-1)))==0) {
				to[i*n + x][0] = (i|(1<<(dist[x]-1)))*n + next[x];
			} else {
				to[i*n + x][0] = -1;
			}
		}
	}
	
	dfs.push(0);

	bool found=false;
	vector<bool> visited_big((1<<k)*n, false);
	visited_big[0]=true;
	while (dfs.size()) {
		unsigned x=dfs.top(); dfs.pop();
		for (int y: to[x]) {
			if (y==-1) continue;

			if (y%n==0) {
				found=true;
				break;
			} else if (!visited_big[y]) {
				visited_big[y]=true;
				dfs.push(y);
			}
		}
	}

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

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:22:22: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   22 |  for (unsigned i=0; i<n-1; i++) {
      |                     ~^~~~
burza.cpp:42:10: warning: comparison of integer expressions of different signedness: 'unsigned int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   42 |     if (a!=parent[x]) {
burza.cpp:69:9: warning: comparison of integer expressions of different signedness: 'unsigned int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   69 |    if (a!=parent[x] && good[a]) dfs.push(a), child.push_back(a);

• 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