oj.uz

Submission #216923

# Submission time Handle Problem Language Result Execution time Memory
216923 2020-03-28T12:51:04 Z Sorting Burza (COCI16_burza) C++14
160 / 160
 215 ms 94328 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 400 + 1;
const int kK = 20 + 1;

vector<int> adj[kN];
bool dp[kN][1 << kK];
vector<int> order;
int tin[kN], tout[kN], depth[kN];

void dfs_order(int u, int parent = -1){
	tin[u] = order.size();
	order.push_back(u);
	depth[u] = parent != -1 ? depth[parent] + 1 : 0;

	for(int to: adj[u]){
		if(to == parent)
			continue;

		dfs_order(to, u);
	}

	tout[u] = order.size() - 1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;
	cin >> n >> k;

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

	for(int i = 0; i < n - 1; ++i){
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs_order(1);

	for(int mask = 0; mask < (1 << (k + 1)); ++mask)
		dp[order.size()][mask] = true;

	for(int i = (int)order.size() - 1; i >= 0; --i){
		for(int mask = 0; mask < (1 << (k + 1)); ++mask){
			if(depth[order[i]] < k){
				dp[i][mask] = dp[i + 1][mask];
				if(dp[i][mask])
					continue;
			}

			if( ((1 << depth[order[i]]) & mask) == 0)
				dp[i][mask] = dp[tout[order[i]] + 1][(mask | (1 << depth[order[i]]))];
		}
	}

	if(dp[1][0])
		cout << "DA\n";
	else
		cout << "NE\n";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11384 KB Output is correct
2 Correct 194 ms 94328 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 90556 KB Output is correct
2 Correct 196 ms 91512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 188 ms 92664 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 92024 KB Output is correct
2 Correct 196 ms 92024 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 23544 KB Output is correct
2 Correct 196 ms 93944 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 2432 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 89056 KB Output is correct
2 Correct 206 ms 91256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 6 ms 2560 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 90872 KB Output is correct
2 Correct 188 ms 90640 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 3200 KB Output is correct
6 Correct 6 ms 2304 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 93048 KB Output is correct
2 Correct 185 ms 90808 KB Output is correct
3 Correct 5 ms 432 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 182 ms 91768 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 21752 KB Output is correct
2 Correct 191 ms 92896 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 432 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 13 ms 3584 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10496 KB Output is correct
2 Correct 196 ms 93744 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 6 ms 3200 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 41720 KB Output is correct
2 Correct 193 ms 93432 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 91 ms 42104 KB Output is correct
6 Correct 6 ms 1792 KB Output is correct