oj.uz

Submission #577206

# Submission time Handle Problem Language Result Execution time Memory
577206 2022-06-14T09:23:20 Z GioChkhaidze Burza (COCI16_burza) C++17
0 / 160
 6 ms 468 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[404][524288];
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;
	if (depth > k) {
		--depth;
		return ;
	}
	L[x] = 1e9, R[x] = -1e9;
	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) {
		L[x] = R[x] = ++ts;
	}
	mv[L[x]].pb({R[x], depth});
	--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:55: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]
   55 |     for (int j = 0; j < mv[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -