oj.uz

Submission #394252

# Submission time Handle Problem Language Result Execution time Memory
394252 2021-04-26T09:03:56 Z ParsaPordastan Burza (COCI16_burza) C++14
160 / 160
 81 ms 10592 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 4 * 100 + 1;
const int LG = 20;

int n, k, st[N], en[N], h[N];
int TM;
int dp[N][1 << LG];
vector <int> adj[N], chk[N];

void DFS(int v, int par) {
	if (h[v] == k - 1) {
		st[v] = TM++;
		en[v] = TM;
		return;
	}
	st[v] = TM;
	for (auto u: adj[v])
		if (u != par) {
			h[u] = h[v] + 1;
			DFS(u, v);
		}
	en[v] = TM;
}

int main() { 
	ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n >> k;
	if (k * k >= n)
		return cout << "DA\n", 0;
	for (int i = 1, v, u; i < n; i++) {
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	h[1] = -1;
	DFS(1, 0);
	//cout << TM << '\n';
	for (int i = 2; i <= n; i++)
		chk[st[i]].push_back(i);
	dp[0][0] = 1;
	for (int i = 0; i < TM; i++)
		for (int mask = 0; mask < (1 << k); mask++) {
			if (!dp[i][mask])
				continue;
			for (auto v: chk[i]) {
				if (mask >> h[v] & 1);
				else {
					//cout << "KHAR\n" << en[v] << ' ' << mask << '\n';
					dp[en[v]][mask + (1 << h[v])] = 1;
				}
			}
		}
	for (int mask = 0; mask < (1 << k); mask++)
		if (dp[TM][mask]) {
			//cout << TM << " " << mask << endl;
			return cout << "DA\n", 0;
		}
	cout << "NE" << '\n';
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1728 KB Output is correct
2 Correct 52 ms 7860 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8472 KB Output is correct
2 Correct 51 ms 8052 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 78 ms 9328 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8900 KB Output is correct
2 Correct 58 ms 7920 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 588 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3020 KB Output is correct
2 Correct 76 ms 10592 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6820 KB Output is correct
2 Correct 65 ms 9288 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8472 KB Output is correct
2 Correct 70 ms 8424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 1356 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 9596 KB Output is correct
2 Correct 66 ms 8520 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 81 ms 9880 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2772 KB Output is correct
2 Correct 62 ms 8504 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1356 KB Output is correct
2 Correct 77 ms 9592 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 2 ms 1356 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4676 KB Output is correct
2 Correct 74 ms 9424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 30 ms 4932 KB Output is correct
6 Correct 1 ms 844 KB Output is correct