oj.uz

Submission #939755

# Submission time Handle Problem Language Result Execution time Memory
939755 2024-03-06T17:37:38 Z vjudge1 Chase (CEOI17_chase) C++17
70 / 100
 202 ms 98496 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
 
bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){YES(1);}
void NO(){YES(0);}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define ld long double
#define pii pair <int , int>
#define all(x) x.begin() , x.end()
#define ff first
#define ss second
#define endl '\n'
 
const int N = 2e5 + 5 ;
const int inf = 1e16 ;
const int mod = 1e9 + 8 ;
const double eps = 1e-8 ;
 
template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}
 
//code
 
int n , m , ans ;
int a[N] , dp[N][103] , c[N] ;
vector <int> g[N] ;
bool vis[N] ;

void dfs ( int v , int p ){
	vis[v] = 1 ;
	for ( int i = 1 ; i <= m ; i ++ ){
		if ( dp[p][i] == -1 ) break ;
		chmax ( dp[v][i] , max(dp[p][i-1]+c[v]-a[p] , dp[p][i]) ) ;
		chmax ( ans , dp[v][i] ) ;
	}
	for ( auto to : g[v] ){
		if ( !vis[to] ){
			dfs(to,v) ;
		}
		
	}
}

void solve(){
	
	cin >> n >> m ;
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 0 ; j <= m ; j ++ ) dp[i][j] = -1 ;
	for ( int i = 1 ; i < n ; i ++ ){
		int x , y ; cin >> x >> y ;
		g[x].push_back(y) ;
		g[y].push_back(x) ;
		c[x] += a[y] ;
		c[y] += a[x] ;
	}
	if ( n <= 1000 ){
		for ( int i = 1 ; i <= n ; i ++ ){
			dfs(i,0) ;
			for ( int j = 1 ; j <= n ; j ++ ) vis[j] = 0 ;
			for ( int j = 1 ; j <= n ; j ++ ) for ( int l = 0 ; l <= m ; l ++ ) dp[j][l] = -1 ;
		}
	}
	else dfs(1,0) ;
	cout << ans ;
}

signed main(){
    ios ;
	int t = 1 ;
	//cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message

chase.cpp: In function 'void fopn(std::string)':
chase.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10716 KB Output is correct
4 Correct 3 ms 10728 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10716 KB Output is correct
4 Correct 3 ms 10728 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 191 ms 10788 KB Output is correct
8 Correct 20 ms 10588 KB Output is correct
9 Correct 17 ms 10588 KB Output is correct
10 Correct 202 ms 11356 KB Output is correct
11 Correct 70 ms 10588 KB Output is correct
12 Correct 32 ms 10584 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 96352 KB Output is correct
2 Correct 117 ms 98496 KB Output is correct
3 Correct 61 ms 95432 KB Output is correct
4 Correct 52 ms 95312 KB Output is correct
5 Correct 100 ms 95384 KB Output is correct
6 Correct 125 ms 95448 KB Output is correct
7 Correct 101 ms 95312 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10716 KB Output is correct
4 Correct 3 ms 10728 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 191 ms 10788 KB Output is correct
8 Correct 20 ms 10588 KB Output is correct
9 Correct 17 ms 10588 KB Output is correct
10 Correct 202 ms 11356 KB Output is correct
11 Correct 70 ms 10588 KB Output is correct
12 Correct 32 ms 10584 KB Output is correct
13 Correct 102 ms 96352 KB Output is correct
14 Correct 117 ms 98496 KB Output is correct
15 Correct 61 ms 95432 KB Output is correct
16 Correct 52 ms 95312 KB Output is correct
17 Correct 100 ms 95384 KB Output is correct
18 Correct 125 ms 95448 KB Output is correct
19 Correct 101 ms 95312 KB Output is correct
20 Incorrect 99 ms 95384 KB Output isn't correct
21 Halted 0 ms 0 KB -