Submission #56341

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
56341	2018-07-11T05:27:57 Z	김세빈(#1599)	Construction of Highway (JOI18_construction)	C++11	Compilation error	0 ms	0 KB

construction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

vector <ll> V[101010], X;
vector <pll> M;
ll A[101010], B[101010], C[101010];
ll D[101010], L[101010], R[101010], K[101010];
ll T[303030], P[101010];
ll n, cnt, sz;

ll dfs_order(ll p)
{
	L[p] = R[p] = ++cnt;
	
	for(auto t: V[p]){
		D[t] = D[p] + 1;
		R[p] = dfs_order(t);
	}
	
	return R[p];
}

void insert(ll p, ll v)
{
	p += sz; T[p] = v;
	for(p>>=1;p;p>>=1){
		T[p] = max(T[p<<1], T[p<<1|1]);
	}
}

ll get_max(ll l, ll r)
{
	ll ret = 0;
	
	l += sz, r += sz;
	for(ret=0;l<r;){
		if(l & 1) ret = max(ret, T[l]);
		if(~r & 1) ret = max(ret, T[r]);
		l = l+1 >> 1;
		r = r-1 >> 1;
	}
	if(l == r) ret = max(ret, T[l]);
	
	return ret;
}

void change(ll p, ll v)
{
	for(;p<=n;p+=p&(-p)){
		P[p] += v;
	}
}

ll get_sum(ll p)
{
	ll ret = 0;
	
	for(;p;p-=p&(-p)){
		ret += P[p];
	}
	
	return ret;
}

int main()
{
	ll i, p, k, s, c, d;
	
	scanf("%lld", &n);
	
	for(sz=1;sz<n;sz<<=1);
	
	for(i=1;i<=n;i++){
		scanf("%lld", C+i);
		X.push_back(C[i]);
	}
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	for(i=1;i<=n;i++){
		C[i] = lower_bound(X.begin(), X.end(), C[i]) - X.begin() + 1;
	}
	
	B[0] = 1;
	for(i=1;i<n;i++){
		scanf("%lld%lld", A+i, B+i);
		V[A[i]].push_back(B[i]);
	}
	
	D[1] = 1;
	dfs_order(1);
	
	for(i=1;i<n;i++){
		M.clear();
		s = 0;
		
		for(p=A[i];p!=0;){
			k = get_max(L[p], R[p]);
			
			c = C[B{k]], d = D[p] - D[K[k]];
			s += get_sum(c - 1) * d;
			change(c, d);
			M.push_back(pll(c, d));
			
			swap(K[k], p);
		}
		
		printf("%lld\n", s);
		
		for(pll t: M) change(t.first, t.second);
		
		insert(L[B[i]], i);
		K[i] = 0;
	}
	
	return 0;
}

Compilation message

construction.cpp: In function 'll get_max(ll, ll)':
construction.cpp:43:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l+1 >> 1;
       ~^~
construction.cpp:44:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r-1 >> 1;
       ~^~
construction.cpp: In function 'int main()':
construction.cpp:105:11: error: expected ']' before '{' token
    c = C[B{k]], d = D[p] - D[K[k]];
           ^
construction.cpp:105:11: error: invalid types 'll [101010] {aka long long int [101010]}[ll [101010] {aka long long int [101010]}]' for array subscript
construction.cpp:71:20: warning: unused variable 'd' [-Wunused-variable]
  ll i, p, k, s, c, d;
                    ^
construction.cpp:122:1: error: expected '}' at end of input
 }
 ^
construction.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
construction.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", C+i);
   ~~~~~^~~~~~~~~~~~~
construction.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", A+i, B+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~