Submission #346703

#	Time	Username	Problem	Language	Result	Execution time	Memory
346703		CaroLinda	Construction of Highway (JOI18_construction)	C++14	100 / 100	310 ms	21092 KiB

construction

#include <bits/stdc++.h>

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

const int MAXN = 1e5+10 ;

using namespace std ;

struct Bit
{

	int bit[MAXN] ;

	void upd(int i, int val) { for(; i < MAXN ; i += i &-i ) bit[i] += val ; }
	int qry(int i )
	{
		int tot = 0 ;
		for(; i > 0 ; i -= i &-i ) tot += bit[i] ;
		return tot ;
	}

} bit ;

int N ;
int C[MAXN] ;
int sub[MAXN] , lvl[MAXN] ;
int parent[MAXN] , myChain[MAXN] , chainHead[MAXN] ;
int chainInd[MAXN] ;
vector<int> adj[MAXN] ;
vector< vector<pair<int,int> > > chain ;

void dfs(int x)
{
	sub[x] = 1 ;
	for(auto e : adj[x] )
	{
		parent[e] = x ;
		lvl[e] = lvl[x] + 1 ;
		dfs(e) ;
		sub[x] += sub[e] ;
	}
}

int currChain = 1 ;
void dfsHld(int x)
{
	
	int bc = -1 ;

	for(auto e : adj[x] )
		if( bc == -1 || sub[bc] < sub[e] ) bc = e ;
	
	if( bc != -1 )
	{
		myChain[bc] = currChain ;
		chainInd[bc] = chainInd[x] + 1 ;
		dfsHld( bc ) ;
	}

	for(auto e : adj[x] )
	{
		if( e == bc ) continue ;

		myChain[e] = ++currChain ;
		chainHead[ currChain ] = e ;
	   chainInd[e] = 1 ;
	   chain.push_back( vector<pair<int,int> >() ) ;

		dfsHld(e) ;

	}
	
}

int main()
{
	vector<int> p ;

	scanf("%d", &N ) ;
	for(int i = 1 ; i <= N ; i++ ) 
	{
		scanf("%d", &C[i] ) ;
		p.push_back(C[i] ) ;
	}

	sort(all(p) ) ;
	p.erase(unique(all(p)) , p.end() ) ;

	for(int i = 1 ; i <= N ; i++ ) C[i] = lower_bound( all(p) , C[i] ) - p.begin() + 1 ;

	vector<int> orderOfInsertion ;

	for(int i = 1 , a , b ; i < N ; i++ )
	{
		scanf("%d %d", &a, &b ) ;
		
		orderOfInsertion.push_back(b) ;

		adj[a].push_back(b) ;

	}
	
	dfs(1) ;

	chain.push_back( vector<pair<int,int> >() ) ;
	chain.push_back( vector<pair<int,int> >() ) ;
	chainHead[1] = myChain[1] = chainInd[1] = 1 ;

	chain[1].push_back( make_pair(1, C[1] ) ) ;

	dfsHld(1) ;

	/*for(int i = 1 ; i <= N ; i++ ) cout << myChain[i] << " " << i<< endl ;
	for(int i = 1 ; i <= currChain ; i++ ) cout << i << " " << chainHead[i] << endl ; */

	for(auto B : orderOfInsertion )
	{
		int A = parent[B] ;

		vector< pair<int,int > > v ;

		ll ans = 0LL ;

		while(A)
		{
			int id = myChain[A] ;
			int went = 0 ;

			int x = sz(v) ;

			for(int i = sz(chain[id] )-1 ; went < chainInd[A] ; i-- )
			{
				if( went + chain[id][i].first > chainInd[A] )
				{
					v.push_back( make_pair(chainInd[A] - went, chain[id][i].second ) ) ;
					chain[id][i].first -= (chainInd[A] - went ) ;

				}
				else
				{
					v.push_back( chain[id][i] ) ;
					chain[id].pop_back() ;
				}

				went += v.back().first ;

			}

			reverse( v.begin() + x , v.end() ) ;
			chain[id].push_back(make_pair(chainInd[A] + (id == myChain[B] ? 1 : 0 ), C[B] ) ) ;

			A = parent[ chainHead[id] ] ;

		}

		if( chainInd[B] == 1 ) chain[ myChain[B] ].push_back( make_pair(1, C[B] ) ) ;

		for(auto e : v )
		{
			ans += (ll)e.first * bit.qry( e.second - 1 ) ;
			bit.upd( e.second , e.first ) ;
		}
		for(auto e : v ) bit.upd(e.second , -e.first ) ;

		printf("%lld\n", ans ) ;

	}	

}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
construction.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |   scanf("%d", &C[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~
construction.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |   scanf("%d %d", &a, &b ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84