Submission #216923

#	Time	Username	Problem	Language	Result	Execution time	Memory
216923		Sorting	Burza (COCI16_burza)	C++14	160 / 160	215 ms	94328 KiB

burza

#include <bits/stdc++.h>

using namespace std;

const int kN = 400 + 1;
const int kK = 20 + 1;

vector<int> adj[kN];
bool dp[kN][1 << kK];
vector<int> order;
int tin[kN], tout[kN], depth[kN];

void dfs_order(int u, int parent = -1){
	tin[u] = order.size();
	order.push_back(u);
	depth[u] = parent != -1 ? depth[parent] + 1 : 0;

	for(int to: adj[u]){
		if(to == parent)
			continue;

		dfs_order(to, u);
	}

	tout[u] = order.size() - 1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;
	cin >> n >> k;

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

	for(int i = 0; i < n - 1; ++i){
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs_order(1);

	for(int mask = 0; mask < (1 << (k + 1)); ++mask)
		dp[order.size()][mask] = true;

	for(int i = (int)order.size() - 1; i >= 0; --i){
		for(int mask = 0; mask < (1 << (k + 1)); ++mask){
			if(depth[order[i]] < k){
				dp[i][mask] = dp[i + 1][mask];
				if(dp[i][mask])
					continue;
			}

			if( ((1 << depth[order[i]]) & mask) == 0)
				dp[i][mask] = dp[tout[order[i]] + 1][(mask | (1 << depth[order[i]]))];
		}
	}

	if(dp[1][0])
		cout << "DA\n";
	else
		cout << "NE\n";
}

• 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