Submission #334707

#	Time	Username	Problem	Language	Result	Execution time	Memory
334707		CaroLinda	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	541 ms	67692 KiB

designated_cities

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

	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] = 0 ;
	}

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

}

Compilation message (stderr)

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: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44