oj.uz

Submission #577201

# Submission time Handle Problem Language Result Execution time Memory
577201 2022-06-14T09:18:38 Z lollipop Burza (COCI16_burza) C++17
80 / 160
 2 ms 2260 KB 
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
#define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
using namespace std ;
const int mod1 =  1000000007 ;
const int mod = 998244353 ; 
const int N = 2e5 + 10 ; 
map < int , int > ma , ma1 ; 
vector < int > v[ 500 ] ;
int dp[ 500 ][ 500 ] ; 
int am[ 500 ] ;
int dn = 0 ; 
int nmb[ 500 ][ 500 ] ; 
vector < int > done[ 500 ] ; 
vector < int > children[ 500 ] ; 
int visited[ 500 ] ;
void dfs( int node , int parent , int height ){
//	cout << height << endl;
	int cnt = 0 ; 
	nmb[ node ][ height ] += 1 ; 
	dn = max( dn , height ) ; 
	done[ height ].pb( node ) ;
	FOR( i , v[ node ].size() ){
	 	int son = v[ node ][ i ] ;
	 	if( son == parent ) continue ; 
	 	dfs( son , node , height + 1 ) ; 
	 	FOR( j , 500 ) nmb[ node ][ j ] += nmb[ son ][ j ] ; 
		children[ node ].pb( son ) ;
		FOR( j , children[ son ].size() ) children[ node ].pb( children[ son ][ j ] ) ; 
	 }
}
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); 
    int n , k ;
    cin >> n >> k ; 
    k -- ; 
    FOR( i , n - 1 ){
    	int x , y ; cin >> x >> y ; 
    	v[ y ].pb( x ) ;
    	v[ x ].pb( y ) ;
	}
	dfs( 1 , -1 , 0 ) ;
 	if( dn <= k ){
		cout << "DA\n" ;
		return 0 ; 
	}
    
    int tt = 0 ;
    for( int i = 1 ; i <= k + 1 ; i ++ ){
    	if( i > dn ) break ;
    	 if( done[ i ].size() <= i && i < k + 2  ){
    	 	tt = 1 ;
    	 	break ;
		 }
         FOR( j , 500 ) visited[ j ] = 0 ;  
		 int cnt = 0 ; 	 
		 int lft = done[ i ].size() ; 
    	 for( int j = 1 ; j <= i ; j ++ ){
    	 	  cnt ++ ; 
    	 	  if( cnt > k ) break ;
    	 	  if( cnt + lft <= k ){
    	 	  	tt = 1 ;
    	 	  	break ;
			  }
			 pair < int , int > mx ;
			 mx.f = 0 ; 
		     FOR( k , done[ j ].size() ){
		     	 int node = done[ j ][ k ] ;
		     	 if( visited[ node ] == 1 ) continue ;
		     	 if( nmb[ node ][ i ] > mx.f ){
		     	 	mx.f = nmb[ node ][ i ] ;
		     	 	mx.s = node ;
				  }
			 }
			 lft -= mx.f ; 
			 visited[ mx.s ] = 1 ; 
			 FOR( k , children[ mx.s ].size() ) visited[ children[ mx.s ][ k ] ] = 1 ;
			 if( cnt + lft <= i ){
    	 	  	tt = 1 ;
    	 	  	break ;
			  }
		 }
    	 
	}
    if( tt == 1 ){
    	cout << "DA" ;
    	return 0 ; 
	}
    cout << "NE\n"; 
}

Compilation message

burza.cpp:10: warning: "FOR" redefined
   10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
      | 
burza.cpp:9: note: this is the location of the previous definition
    9 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
      | 
burza.cpp:11: warning: "FOR" redefined
   11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
      | 
burza.cpp:10: note: this is the location of the previous definition
   10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
      | 
burza.cpp: In function 'void dfs(long long int, long long int, long long int)':
burza.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
......
   31 |  FOR( i , v[ node ].size() ){
      |       ~~~~~~~~~~~~~~~~~~~~               
burza.cpp:31:2: note: in expansion of macro 'FOR'
   31 |  FOR( i , v[ node ].size() ){
      |  ^~~
burza.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
......
   37 |   FOR( j , children[ son ].size() ) children[ node ].pb( children[ son ][ j ] ) ;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~        
burza.cpp:37:3: note: in expansion of macro 'FOR'
   37 |   FOR( j , children[ son ].size() ) children[ node ].pb( children[ son ][ j ] ) ;
      |   ^~~
burza.cpp:27:6: warning: unused variable 'cnt' [-Wunused-variable]
   27 |  int cnt = 0 ;
      |      ^~~
burza.cpp: In function 'int main()':
burza.cpp:59:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |       if( done[ i ].size() <= i && i < k + 2  ){
      |           ~~~~~~~~~~~~~~~~~^~~~
burza.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
......
   75 |        FOR( k , done[ j ].size() ){
      |             ~~~~~~~~~~~~~~~~~~~~         
burza.cpp:75:8: note: in expansion of macro 'FOR'
   75 |        FOR( k , done[ j ].size() ){
      |        ^~~
burza.cpp:11:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
......
   85 |     FOR( k , children[ mx.s ].size() ) visited[ children[ mx.s ][ k ] ] = 1 ;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
burza.cpp:85:5: note: in expansion of macro 'FOR'
   85 |     FOR( k , children[ mx.s ].size() ) visited[ children[ mx.s ][ k ] ] = 1 ;
      |     ^~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 2 ms 2004 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 2 ms 1908 KB Output is correct
6 Incorrect 1 ms 724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 1 ms 2036 KB Output is correct
5 Incorrect 1 ms 1876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 2032 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Incorrect 1 ms 724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 2 ms 2004 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2032 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 2040 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 1 ms 1264 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1912 KB Output is correct
3 Correct 1 ms 2004 KB Output is correct
4 Correct 2 ms 2260 KB Output is correct
5 Correct 2 ms 1908 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1648 KB Output is correct
2 Correct 1 ms 1972 KB Output is correct
3 Correct 1 ms 2040 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 2004 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 2032 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Incorrect 1 ms 1656 KB Output isn't correct
6 Halted 0 ms 0 KB -