oj.uz

Submission #577222

# Submission time Handle Problem Language Result Execution time Memory
577222 2022-06-14T09:37:23 Z GioChkhaidze Burza (COCI16_burza) C++14
160 / 160
 21 ms 3020 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;

const int N = 404;

bool f[N][527288];
int n, k, ts, depth, L[N], R[N];
vector < pair < int , int > > mv[N];
vector < int > v[N];

void dfs(int x, int p) {
	++depth;
	L[x] = 1e9, R[x] = -1e9;
	if (depth > k + 1) {
		--depth;
		return ;
	}
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to == p) continue;
		dfs(to, x);
		L[x] = min(L[x], L[to]);
		R[x] = max(R[x], R[to]);
	}
	if (depth == k + 1) {
		L[x] = R[x] = ++ts;
	}
	if (L[x] != 1e9 && x != p) {
		mv[L[x]].pb({R[x], depth - 2});
	}
	--depth;
}

int main() {
	cin >> n >> k;
	if (k * k >= n) {
		cout << "DA\n";
	}
		else {
		for (int i = 1; i < n; ++i) {
			int a, b;
			cin >> a >> b;
			v[a].pb(b);
			v[b].pb(a);
		}

		dfs(1, 1);
		f[0][0] = true;
		for (int i = 1; i <= ts; ++i) {
			for (int ms = 0; ms < (1 << k); ++ms) {
				if (!f[i - 1][ms]) continue;
				for (int j = 0; j < mv[i].size(); ++j) {
					int jmp = mv[i][j].f;
					int dep = mv[i][j].s;
					if ((ms >> dep) & 1) continue;
					f[jmp][(ms | (1 << dep))] = true;
				}
			}	
		}

		for (int ms = 0; ms < (1 << k); ++ms) {
			if (f[ts][ms]) {
				cout << "DA\n";
				exit(0);
			}
		}

		cout << "NE\n";
	}
}

Compilation message

burza.cpp: In function 'void dfs(int, int)':
burza.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
burza.cpp: In function 'int main()':
burza.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int j = 0; j < mv[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 14 ms 2324 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2576 KB Output is correct
2 Correct 12 ms 2380 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 16 ms 2772 KB Output is correct
6 Correct 1 ms 724 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2620 KB Output is correct
2 Correct 14 ms 2252 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 21 ms 3020 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 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 12 ms 2148 KB Output is correct
2 Correct 15 ms 2816 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 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2728 KB Output is correct
2 Correct 14 ms 2616 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2644 KB Output is correct
2 Correct 15 ms 2636 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 14 ms 2900 KB Output is correct
6 Correct 1 ms 724 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 18 ms 2516 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 15 ms 2772 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 596 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 7 ms 1544 KB Output is correct
2 Correct 15 ms 2756 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 8 ms 1520 KB Output is correct
6 Correct 1 ms 468 KB Output is correct