oj.uz

Submission #701717

# Submission time Handle Problem Language Result Execution time Memory
701717 2023-02-22T02:31:43 Z thomasqm Burza (COCI16_burza) C++17
160 / 160
 917 ms 417372 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <list>
#include <array>
#include <set>
#include <map>
#include <chrono>
#include <stack>
#include <random>
#include <climits>
#include <algorithm>
#include <tgmath.h>

using namespace std;

int main() {
	int n,k; cin>>n>>k;
	vector<vector<unsigned>> adj(n);
	for (unsigned i=0; i<n-1; i++) {
		unsigned a,b; cin>>a>>b; a--, b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

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

	vector<array<int, 2>> to((1<<k)*n);
	vector<int> parent(n, 0), next(n, 0), dist(n, 0);
	vector<bool> visited(n, false), good(n,false);

	stack<unsigned> dfs({0});
	while (dfs.size()) {
		unsigned x = dfs.top();

		if (!visited[x]) {
			for (unsigned a: adj[x]) {
				if (a!=parent[x]) {
					parent[a]=x;
					dist[a]=dist[x]+1;
					dfs.push(a);
				}
			}

			if (dist[x]>=k) good[x]=true;
			visited[x]=true;
			continue;
		} else if (!good[x]) {
			dfs.pop();
			continue;
		} else {
			good[parent[x]]=true;
			dfs.pop();
		}
	}

	dfs.push(0);

	vector<int> child;
	while (dfs.size()) {
		unsigned x = dfs.top(); dfs.pop();

		child.clear();
		for (unsigned a: adj[x]) {
			if (a!=parent[x] && good[a]) dfs.push(a), child.push_back(a);
		}
		
		for (unsigned i=0; i<child.size(); i++) {
			next[child[i]] = i+1==child.size() ? next[x] : child[i+1];
		}

		for (int i=0; i<(1<<k); i++) {
			to[i*n + x][1] = child.size() ? (i*n + child[0]) : -1;
			if (dist[x]>0 && dist[x]<=k && (i&(1<<(dist[x]-1)))==0) {
				to[i*n + x][0] = (i|(1<<(dist[x]-1)))*n + next[x];
			} else {
				to[i*n + x][0] = -1;
			}
		}
	}
	
	dfs.push(0);

	bool found=false;
	vector<bool> visited_big((1<<k)*n, false);
	visited_big[0]=true;
	while (dfs.size()) {
		unsigned x=dfs.top(); dfs.pop();
		for (int y: to[x]) {
			if (y==-1) continue;

			if (y%n==0) {
				found=true;
				break;
			} else if (!visited_big[y]) {
				visited_big[y]=true;
				dfs.push(y);
			}
		}
	}

	cout<<(found ? "DA\n" : "NE\n");
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:22:22: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   22 |  for (unsigned i=0; i<n-1; i++) {
      |                     ~^~~~
burza.cpp:42:10: warning: comparison of integer expressions of different signedness: 'unsigned int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   42 |     if (a!=parent[x]) {
burza.cpp:69:9: warning: comparison of integer expressions of different signedness: 'unsigned int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   69 |    if (a!=parent[x] && good[a]) dfs.push(a), child.push_back(a);

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 40908 KB Output is correct
2 Correct 797 ms 417128 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 688 KB Output is correct
6 Correct 1 ms 280 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 396352 KB Output is correct
2 Correct 815 ms 398284 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 892 ms 403644 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 401508 KB Output is correct
2 Correct 773 ms 401616 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 0 ms 296 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 98216 KB Output is correct
2 Correct 917 ms 417372 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 424 KB Output is correct
6 Correct 0 ms 300 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 383912 KB Output is correct
2 Correct 770 ms 396220 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 684 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 399428 KB Output is correct
2 Correct 776 ms 393228 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 #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 406616 KB Output is correct
2 Correct 752 ms 395244 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 811 ms 396312 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 87780 KB Output is correct
2 Correct 800 ms 408804 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 424 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 36612 KB Output is correct
2 Correct 793 ms 412888 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 2 ms 980 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 173296 KB Output is correct
2 Correct 795 ms 411924 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 359 ms 175388 KB Output is correct
6 Correct 1 ms 340 KB Output is correct