oj.uz

답안 #1052926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052926 2024-08-11T06:04:41 Z coolsentenceidontremember Burza (COCI16_burza) C++17
160 / 160
 24 ms 1008 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){
//	cout << u << ' ' << p << ' ' << lvl << '\n'; 
	segment[u] = {inf, -inf};
	depth[lvl].push_back(u);
//	cout << u << ' ' << lvl << '\n';
	if (lvl == max_lvl){
		cnt++;
		segment[u] = {cnt, cnt}; 
	//	cout << u << ' ' << cnt << '\n';
		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" << '\n';
   	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);
				}
			}
		}
	  
   }
for (int i = 0; i < (1<<k); i++){
	if (dp[i] == cnt) return cout << "DA", 0;
}
return cout << "NE", 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
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 19 ms 1008 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 856 KB Output is correct
2 Correct 19 ms 992 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 20 ms 1008 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 860 KB Output is correct
2 Correct 19 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 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 19 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 856 KB Output is correct
2 Correct 19 ms 1000 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 412 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1000 KB Output is correct
2 Correct 20 ms 856 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 860 KB Output is correct
2 Correct 19 ms 996 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 20 ms 1004 KB Output is correct
6 Correct 1 ms 604 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 20 ms 1008 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 23 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 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 21 ms 984 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 748 KB Output is correct
6 Correct 0 ms 348 KB Output is correct