oj.uz

Submission #537410

# Submission time Handle Problem Language Result Execution time Memory
537410 2022-03-15T05:05:55 Z mmonteiro Burza (COCI16_burza) C++17
160 / 160
 234 ms 207212 KB 
#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;

#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAX = 403;

int n, k;
vector<int> G[MAX];
int tin[MAX], tout[MAX], level[MAX], timer;
vector<int> bucket[MAX];
int dp[10 + (1 << 20)][MAX];

void dfs(int v, int p) {
	if(level[v] >= 0)
		bucket[level[v]].push_back(v);

	tin[v] = timer + 1;
	for(int u : G[v]) {
		if(u != p) {
			level[u] = level[v] + 1;
			if(level[u] < k) {
				dfs(u, v);
			}
		}
	}
	if(level[v] == k - 1)	
		timer++;

	tout[v] = timer;
}

void solve() {
	cin >> n >> k;
	for(int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v; --u; --v;
		G[u].push_back(v);
		G[v].push_back(u);
	}

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

	level[0] = -1;
	dfs(0, -1);

	for(int i = 0; i <= k; ++i)
		sort(bucket[i].begin(), bucket[i].end(), [&](int a, int b)
			{
				return tin[a] < tin[b];
			}
		);

	for(int i = 0; i < (1 << k); ++i)
		dp[i][0] = 1;

	for(int i = 1; i < (1 << k); ++i) 
		for(int j = 0; j < k; ++j) 
			if(i & (1 << j)) 
				for(int u : bucket[j]) 
					if(dp[i ^ (1 << j)][ tin[u] - 1])
						dp[i][ tout[u] ] = 1;		

	bool flag = false;
	for(int i = 0; i < (1 << k); ++i)
		if(dp[i][timer])
			flag = true;

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

int32_t main() {

	fastio;
	solve();

	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26192 KB Output is correct
2 Correct 211 ms 207088 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 207084 KB Output is correct
2 Correct 203 ms 207096 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 224 ms 207108 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 207004 KB Output is correct
2 Correct 203 ms 207088 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 52052 KB Output is correct
2 Correct 207 ms 206976 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 207088 KB Output is correct
2 Correct 199 ms 207096 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 207096 KB Output is correct
2 Correct 196 ms 207068 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 356 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 207212 KB Output is correct
2 Correct 198 ms 206972 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 222 ms 207016 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 52052 KB Output is correct
2 Correct 211 ms 207096 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26204 KB Output is correct
2 Correct 234 ms 207088 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 724 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 103724 KB Output is correct
2 Correct 204 ms 207096 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 97 ms 103720 KB Output is correct
6 Correct 0 ms 340 KB Output is correct