oj.uz

Submission #1052899

# Submission time Handle Problem Language Result Execution time Memory
1052899 2024-08-11T05:42:57 Z coolsentenceidontremember Burza (COCI16_burza) C++17
0 / 160
 30 ms 1012 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("O3", "unroll-loops")


#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"
#define precision(x) fixed << setprecision((x))
#define check_ok() cout << "it aight" << '\n'
using namespace std;



void setIO(string s = ""){
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 if (!s.empty()){
	freopen((s+".in").c_str(), "r", stdin);
	freopen((s+".out").c_str(), "w", stdout);
	}
}


const int N = 400;
const int inf = 1000;
pair<int, int> segment[N+1];
vector<int> adj[N+1];
vector<int> depth[N+1];
int cnt = 0;

void dfs(int u, int p, int lvl, const int &max_lvl){
	segment[u] = {inf, -inf};
	depth[lvl].push_back(u);
	if (lvl == max_lvl){
		cnt++;
		segment[u] = {u, u}; 
		//comp[u] = cnt;
		return;
	}
	
	for (int v : adj[u]){
		if (v != p) dfs(v, u, lvl+1, max_lvl);
		segment[u].ff = min(segment[u].ff, segment[v].ff);
		segment[u].ss = max(segment[u].ss, segment[v].ss);
	}
	return;
}





int main(){
   int n, k;
   cin >> n >> k;
   for (int i = 1; i < n; i++){
   	 int u, v;
   	 cin >> u >> v;
   	 adj[u].push_back(v);
   	 adj[v].push_back(u);
   }   
   if (k*k >= n){
   	cout << "DA";
   	return 0;
   }
   
   dfs(1, -1, 0, k);
   vector<int> dp(1<<k, 0);
   for (int mask = 0; mask < (1<<k); mask++){
   	 for (int b=0; b < k; b++){
   	 	if (mask & (1<<b)){
   	 		int prev = dp[mask^(1<<b)];
   	 		for (int u : depth[b+1]){
   	 			if (segment[u].ff <= prev+1) dp[mask] = max(dp[mask], segment[u].ss);
				}
			}
		}
	  if (dp[mask] == cnt){
	  	cout << "DA";
	  	return 0;
	  }
   }
   cout << "NE";
   return 0;
}

Compilation message

burza.cpp: In function 'void setIO(std::string)':
burza.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen((s+".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burza.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  freopen((s+".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 24 ms 1000 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 860 KB Output is correct
2 Correct 19 ms 1000 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 16 ms 1000 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1000 KB Output is correct
2 Correct 20 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 612 KB Output is correct
2 Correct 30 ms 1004 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 860 KB Output is correct
2 Correct 20 ms 1004 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 856 KB Output is correct
2 Correct 16 ms 856 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 860 KB Output is correct
2 Correct 18 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 18 ms 1000 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 17 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 19 ms 1012 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 768 KB Output is correct
2 Correct 21 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 8 ms 600 KB Output isn't correct
6 Halted 0 ms 0 KB -