oj.uz

Submission #334704

# Submission time Handle Problem Language Result Execution time Memory
334704 2020-12-09T20:37:50 Z CaroLinda Designated Cities (JOI19_designated_cities) C++14
16 / 100
 507 ms 73836 KB 
#include <bits/stdc++.h>

#define debug printf
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )

const int MAXN = 2e5+10 ;
const ll inf = 1e18+10LL ;

using namespace std ;

int N , known ;
int ans[MAXN] ;
vector< pair<int,ll> > adj[MAXN] ;
ll ans1, ans2 , sumOfAll ;
ll prof[MAXN] , sub[MAXN] ;
bool spinned[MAXN] ;
vector<ll> leaves ;

void dfs1(int x, int parent )
{

	for(auto e : adj[x] )
	{
		if( e.first == parent ) continue ;

		dfs1(e.first,x) ;
	
	   sub[x] += sub[e.first] + e.second ;
		prof[x] = max(prof[x] , prof[e.first] + e.second ) ;

	}	
}

void dfs2(int x)
{
	spinned[x] = true ;
	sub[x] = 0 ;

	int tam = sz(adj[x] ) ;
	vector<ll> pref, suf ;

	for(int i = 0 ; i < tam ; i++ )
	{
		pref.push_back( prof[ adj[x][i].first ] + adj[x][i].second ) ;
		suf.push_back( prof[ adj[x][i].first ] + adj[x][i].second ) ;

		sub[x] += sub[ adj[x][i].first ] + adj[x][i].second ;
	}

	for(int i = 1 , j = tam-2 ; i < tam ; i++ , j-- ) 
	{
		pref[i] = max(pref[i] , pref[i-1] ) ;
		suf[j] = max(suf[j], suf[j+1] ) ;
	}

	prof[x] = suf[0] ;

	ans1 = min(ans1, sub[x] ) ;

	if(ans2 >= sub[x] - prof[x] && tam == 1 )
	{
		ans2 = sub[x] - prof[x] ;		
		known = x ;
	}

	for(int i = 0 ; i < tam ; i++ )
	{

		if( spinned[ adj[x][i].first ] ) continue ;

		prof[x] = 0 ;
		if( i ) prof[x] = max( pref[i-1], prof[x] ) ;
		if( i+1 < tam ) prof[x] = max(prof[x], suf[i+1] ) ;
		
		ll saveSubX = sub[x] ;
		ll saveSubChild = sub[ adj[x][i].first ] ;

		sub[x] -= sub[ adj[x][i].first ] + adj[x][i].second ;

		dfs2( adj[x][i].first ) ;

		sub[x] = saveSubX ;
		sub[ adj[x][i].first ] = saveSubChild ;

	}  
     
}

ll dfs3(int x, int parent)
{
	sub[x] = 0 ;
	
	vector< pair<ll,ll> > children ;

	for(auto e : adj[x] )
	{
		if(e.first == parent ) continue ;

		children.push_back( make_pair(dfs3(e.first,x)+e.second, e.second) ) ;
		sub[x] += sub[e.first] + e.second ;
	}

	sort(all(children) ) ;

	for(int i = 0 ; i < sz(children) - 1 ; i++ )
		leaves.push_back(children[i].first - children[i].second ) ;

	return (sz(children) == 0) ? 0LL : children.back().first ;

}

int main()
{
	scanf("%d", &N ) ;
	for(int i = 0 , u , v , uv, vu ; i < N-1 ; i++ )
	{
		scanf("%d %d %d %d", &u, &v, &uv, &vu ) ;

		adj[u].push_back( make_pair(v,(ll)uv) ) ;
		adj[v].push_back( make_pair(u,(ll)vu) ) ;

	}

	ans1 = ans2 = inf ;

	dfs1(1,-1) ;
	dfs2(1) ;
	leaves.push_back(dfs3(known,-1) ) ;

	int Q ;
	scanf("%d", &Q ) ;

	sort(all(leaves) ) ;
	reverse( all(leaves) ) ;

	vector<ll> ans(N+1) ;

	ans[1] = ans1 ;
	ans[2] = sub[ known ] - leaves[0] ;

	for(int i = 1 , j = 3 ; j <= N ; i++ , j++ )
	{
		if( i < sz(leaves) )
			ans[j] = ans[j-1] - leaves[i] ;		
		else ans[j] = ans[j-1] ;
	}

	for(int i = 0 , x ; i < Q ; i++ )
	{
		scanf("%d", &x ) ;
		printf("%lld\n", ans[x] ) ;
	}  

}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
designated_cities.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |   scanf("%d %d %d %d", &u, &v, &uv, &vu ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |  scanf("%d", &Q ) ;
      |  ~~~~~^~~~~~~~~~~
designated_cities.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |   scanf("%d", &x ) ;
      |   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Incorrect 3 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 383 ms 27448 KB Output is correct
3 Correct 507 ms 65572 KB Output is correct
4 Correct 374 ms 26080 KB Output is correct
5 Correct 376 ms 27956 KB Output is correct
6 Correct 426 ms 33384 KB Output is correct
7 Correct 318 ms 28268 KB Output is correct
8 Correct 495 ms 66796 KB Output is correct
9 Correct 238 ms 31072 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 387 ms 27488 KB Output is correct
3 Correct 504 ms 73836 KB Output is correct
4 Correct 374 ms 25952 KB Output is correct
5 Correct 371 ms 27988 KB Output is correct
6 Correct 416 ms 34284 KB Output is correct
7 Correct 251 ms 31700 KB Output is correct
8 Correct 462 ms 51692 KB Output is correct
9 Correct 245 ms 30680 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Incorrect 3 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 383 ms 27448 KB Output is correct
3 Correct 507 ms 65572 KB Output is correct
4 Correct 374 ms 26080 KB Output is correct
5 Correct 376 ms 27956 KB Output is correct
6 Correct 426 ms 33384 KB Output is correct
7 Correct 318 ms 28268 KB Output is correct
8 Correct 495 ms 66796 KB Output is correct
9 Correct 238 ms 31072 KB Output is correct
10 Correct 3 ms 5100 KB Output is correct
11 Correct 387 ms 27488 KB Output is correct
12 Correct 504 ms 73836 KB Output is correct
13 Correct 374 ms 25952 KB Output is correct
14 Correct 371 ms 27988 KB Output is correct
15 Correct 416 ms 34284 KB Output is correct
16 Correct 251 ms 31700 KB Output is correct
17 Correct 462 ms 51692 KB Output is correct
18 Correct 245 ms 30680 KB Output is correct
19 Correct 3 ms 5100 KB Output is correct
20 Incorrect 364 ms 27360 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Incorrect 3 ms 5100 KB Output isn't correct
3 Halted 0 ms 0 KB -