oj.uz

Submission #1036761

# Submission time Handle Problem Language Result Execution time Memory
1036761 2024-07-27T16:25:56 Z ef10 Burza (COCI16_burza) C++17
160 / 160
 44 ms 976 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int N, K;
vector<int> dn[401];
vector<int> adj[401];
map<int,int> leaf;
vector<int> cover[401];
pair<int,int> interval[401];
int dp[1<<20];

void dfs(int c, int p, int d) {
	dn[d].push_back(c);
	if (d == K) {
		leaf[c]=leaf.size();
		cover[c].push_back(c);
		return;
	}
	for (auto n : adj[c]) {
		if (n==p) continue;
		dfs(n,c,d+1);
		for (auto l : cover[n]) {
			cover[c].push_back(l);
		}
	}
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N-1; i++) {
		int a,b; cin >> a >> b;
		a--;b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	if (K*K>N) {
		cout << "DA" << endl;
		return 0;
	}
	dfs(0,0,0);
	/*cout << "cover" << endl;
	for (int i = 0; i < N; i++) {
		cout << i << ": ";
		for (auto n : cover[i]) {
			cout << n << " ";
		}
		cout << endl;
	}
	cout << "leaf" << endl;
	for (auto e : leaf) {
		cout << e.first << "/" << e.second << endl;
	}
	cout << "dn" << endl;
	for (int i =0; i <= K; i++) {
		cout << i << ": ";
		for (auto e : dn[i]) {
			cout << e << " ";
		}
		cout << endl;
	}*/
	for (int i = 0; i < N; i++) {
		if (cover[i].size()== 0) {
			interval[i]=make_pair(-1,-1);
			continue;
		}
		interval[i]=make_pair(leaf[cover[i][0]],leaf[cover[i][cover[i].size()-1]]);
	}
	/*cout << "interval" << endl;
	for (int i = 0; i < N; i++) {
		cout << i << "/" << interval[i].first << "/" << interval[i].second << endl;
	}*/
	for (int i = 0; i < (1<<K); i++) {
		for (int j = 0; j < K; j++) {
			if (!(i & (1<<j))) continue;
			int prev = dp[i & ~(1<<j)];
			for (auto o : dn[j+1]) {
				if (interval[o].first <= prev) {
					dp[i] = max(dp[i],interval[o].second+1);
				}
			}
		}
		//cout << "dp["<<i<<"] = " << dp[i] << endl;
		if (dp[i] == leaf.size()) {
			cout << "DA" << endl;
			return 0;
		}
	}
	cout << "NE" << endl;
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:85:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   if (dp[i] == leaf.size()) {
      |       ~~~~~~^~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 26 ms 968 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 972 KB Output is correct
2 Correct 25 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 25 ms 888 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 860 KB Output is correct
2 Correct 25 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 604 KB Output is correct
2 Correct 28 ms 948 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB Output is correct
2 Correct 24 ms 856 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 860 KB Output is correct
2 Correct 41 ms 788 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 400 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 860 KB Output is correct
2 Correct 44 ms 852 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 25 ms 960 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 604 KB Output is correct
2 Correct 27 ms 796 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 25 ms 976 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB Output is correct
2 Correct 26 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 19 ms 616 KB Output is correct
6 Correct 1 ms 348 KB Output is correct