oj.uz

Submission #520861

# Submission time Handle Problem Language Result Execution time Memory
520861 2022-01-31T09:04:34 Z Cantfindme Burza (COCI16_burza) C++17
160 / 160
 11 ms 1376 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end() 

const int maxn = 410;
const int mod = 1e9+7; 

typedef long double ld;
const ld INF = 10005;

int n, K;
vector <int> adjlist[maxn];
int best[maxn][21];
int dp[1 << 20];

int co = 0;

void dfs(int x, int d, int p) {
	if (d == K - 1) {
		best[co][K-1] = co+1;
		co++;
		return;
	}
	
	int pref = co;
	
	for (auto i: adjlist[x]) if (i != p) {
		dfs(i, d + 1, x);
	}
	
	int post = co;
	for (int i = pref; i < post; i++) {
		best[i][d] = post;
	}
}

int32_t main() {
	FAST
	cin >> n >> K;
	for (int i =0;i<n-1;i++) {
		int a,b; cin >> a >> b;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
	
	if (n - 1 < K * (K+1)) {
		cout << "DA";
		return 0;
	}
	
	dfs(1, -1, -1); //node 1 is depth -1 so that its children are depth 0
	
	
	for (int bm = 1; bm < (1 << K); bm++) {
		int res = 0;
		for (int d = 0; d < K; d++) {
			if (~bm & (1 << d)) continue;
			res = max(res, best[dp[bm ^ (1 << d)]][d]);
		}
		dp[bm] = res;
		if (res == co) {
			cout << "DA";
			return 0;
		}
	}
	cout << "NE";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 8 ms 1304 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1316 KB Output is correct
2 Correct 8 ms 1360 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 8 ms 1376 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1360 KB Output is correct
2 Correct 8 ms 1360 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 8 ms 1360 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1360 KB Output is correct
2 Correct 8 ms 1312 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1308 KB Output is correct
2 Correct 9 ms 1360 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1300 KB Output is correct
2 Correct 8 ms 1360 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 8 ms 1360 KB Output is correct
6 Correct 1 ms 328 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 8 ms 1292 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 11 ms 1340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct
2 Correct 8 ms 1352 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 1 ms 312 KB Output is correct