oj.uz

Submission #727043

# Submission time Handle Problem Language Result Execution time Memory
727043 2023-04-19T23:41:09 Z beaboss Burza (COCI16_burza) C++14
160 / 160
 493 ms 972 KB 
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;

const int maxn = 401;

int depth[maxn];
vector<int> adj[maxn];

vector<int> newadj[maxn];

void findD(int cur, int d, int p) {
	depth[cur]=d;
	for (auto val: adj[cur]) {
		if (val != p) findD(val, d+ 1, cur);
	}
}
bool v[maxn];

void createTree(int cur) {
	if (v[cur]) return;
	v[cur]=true;
	for (auto val: adj[cur]) {
		// assert(cur != val);
		if (depth[val] == depth[cur]-1) {
			// cout << cur << val << endl;
			newadj[cur].pb(val);
			newadj[val].pb(cur);
			createTree(val);
		}
	}
}

int leafcounter = -1;

pair<int, int> ranges[maxn];

pair<int, int> assignRange(int cur, int p) {
	if (newadj[cur].size() == 1) {
		leafcounter++;
		ranges[cur] = {leafcounter, leafcounter};
		return {leafcounter, leafcounter};
	}
	pair<int, int> rval = {10000000, -1};
	for (auto val: newadj[cur]) {
		if (val != p) {
			auto cval = assignRange(val, cur);
			rval.f = min(rval.f, cval.f);
			rval.s = max(rval.s, cval.s);
		}
	}

	ranges[cur] = rval;
	return rval;


}

int main() {
	
	int  n, k;
	cin >> n >> k;

	if (k * k > n) {
		cout << "DA" << endl;
		return 0;
	}

	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);
	}

	findD(0, -1, -1);

	for (int i = 0; i < n; i++) {
		if (depth[i] == k-1) {
			createTree(i);
		}
	}

	assignRange(0, -1);

	
	vector<int> dp((1 << k), -1);
	dp[0] = 0;

	for (int i = 0; i < (1 << k); i++) {
		for (int j = 0; j < k; j++) {
			if ((1 << j) & i) {
				int curdp = 0;
				for (int nxt = 0; nxt < n;nxt++) {
					if (depth[nxt] == j && ranges[nxt].f <= dp[i ^ (1 << j)]) {
						curdp = max(curdp, ranges[nxt].s + 1);
					}
				}
				dp[i] = max(dp[i], curdp);
			}
		}
		if (dp[i] == leafcounter + 1) {
			cout << "DA" << endl;
			return 0;
		}
	}
	cout << "NE" << endl;

	



	
	
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 384 KB Output is correct
2 Correct 493 ms 856 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 856 KB Output is correct
2 Correct 432 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 449 ms 852 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 860 KB Output is correct
2 Correct 421 ms 852 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 472 KB Output is correct
2 Correct 436 ms 860 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 860 KB Output is correct
2 Correct 423 ms 972 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 860 KB Output is correct
2 Correct 428 ms 856 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 856 KB Output is correct
2 Correct 431 ms 856 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 427 ms 872 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 468 KB Output is correct
2 Correct 433 ms 856 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 340 KB Output is correct
2 Correct 438 ms 860 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 280 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 596 KB Output is correct
2 Correct 456 ms 972 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 182 ms 600 KB Output is correct
6 Correct 1 ms 340 KB Output is correct