oj.uz

Submission #1010908

# Submission time Handle Problem Language Result Execution time Memory
1010908 2024-06-29T14:05:54 Z WhiteZeros Burza (COCI16_burza) C++17
160 / 160
 32 ms 936 KB 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define task "coci1617_r2_burza"
const int N = 4e2 + 1 , M = 20 , inf = 1e9 ; 
int n , k , stt = 0; 
vector<int> D[N] , depth[M] , cover[N];   
int dp[1 << M] , tin[N] , tout[N] , pos[N];
void maximize(int &a , int b){
    if(a < b) a = b ; 
}
void minimize(int &a , int b){
    if(a > b) a = b ; 
}
void dfs(int u , int p , int h){
    depth[h].push_back(u) ;
    if(h == k){
        tin[u] = tout[u] = ++stt ;  
        return ; 
    }
    for(int v : D[u]){
        if(v == p) continue;    
        dfs(v , u , h + 1); 
        minimize(tin[u] , tin[v]) ; 
        maximize(tout[u] , tout[v]) ; 
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    if(ifstream(task".INP")){
        freopen(task".INP","r",stdin) ; 
        freopen(task".OUT","w",stdout) ;
    }
    cin >> n >> k ;
    if(k * k >= n){
        cout <<"DA" ; 
        return 0; 
    }
    for(int i = 1 ; i <= n ; i++) tin[i] = inf ; 
    for(int i = 1 ; i < n ; i++){
        int u , v ; 
        cin >> u >> v ; 
        D[u].push_back(v) ;
        D[v].push_back(u) ; 
    }
    dfs(1 , 0 , 0) ; 
    dp[0] = 0 ; 
	for (int i = 1; i < (1 << k); i++) {
		for (int j = 0; j < k; j++) {
			if ((i >> j & 1)) {
				int prev = dp[i ^ (1 << j)];
				for (int v : depth[j + 1]) {
					if (tin[v] <= prev + 1) {
						dp[i] = max(dp[i], tout[v]);
					}
				}
			}
		}

		if (dp[i] == stt) {
			cout << "DA";
			return 0;
		}
	}

	cout << "NE";
    return 0;
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(task".INP","r",stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
burza.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(task".OUT","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 28 ms 856 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 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

# Verdict Execution time Memory Grader output
1 Correct 24 ms 860 KB Output is correct
2 Correct 24 ms 856 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 24 ms 884 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 860 KB Output is correct
2 Correct 24 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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 26 ms 908 KB Output is correct
3 Correct 1 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 #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB Output is correct
2 Correct 24 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 #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 864 KB Output is correct
2 Correct 25 ms 912 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 #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 860 KB Output is correct
2 Correct 24 ms 856 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 24 ms 768 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 588 KB Output is correct
2 Correct 32 ms 848 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 344 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 26 ms 852 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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 600 KB Output is correct
2 Correct 31 ms 936 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 12 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct