제출 #1052926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052926		coolsentenceidontremember	Burza (COCI16_burza)	C++17	160 / 160	24 ms	1008 KiB

burza

#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;
}
                 

컴파일 시 표준 에러 (stderr) 메시지

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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16