Submission #82608

#	Time	Username	Problem	Language	Result	Execution time	Memory
82608		wzy	Construction of Highway (JOI18_construction)	C++11	100 / 100	781 ms	124116 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define piii pair<pii, int>
const int N = 100505;
int ch[N] , pai[N] , C[N] , sz[N], in[N] , tempo = 0 , rinv[N + 100];
vector<int> adj[N];
vector<pii> edge;
deque<piii> Sx[N];
int n;
vector<pii> elements;
void dfs(int x , int y){
	sz[x] = 1 ;
	pai[x] = -1;
	if(x != y) pai[x] = y;
	for(auto &p : adj[x]){
		if(p == y) continue;
		dfs(p, x);
		sz[x] += sz[p];
		if(adj[x][0] == y || sz[adj[x][0]] < sz[p]) swap(p, adj[x][0]);
	}
}

void dfs_hld(int x , int y){
	in[x] = ++tempo;
	if(x == y) ch[x] = 1;
	rinv[tempo] = x;
	for(auto p : adj[x]){
		if(p ==  y) continue;
		if(p == adj[x][0]) ch[p] = ch[x];
		else ch[p] = p;
		dfs_hld(p, x);
	}
}

void getX(int x){
	vector<pii> selements;
	for(auto p : Sx[ch[x]]){
		if(p.F.S <= in[x]){
			selements.push_back(pii(p.S , p.F.S - p.F.F +1));
		}
		else if(p.F.F <= in[x]){
			selements.push_back(pii(p.S , in[x] - p.F.F + 1));
		}
		else break;
	}
	reverse(selements.begin() , selements.end());
	for(auto p : selements){
		elements.push_back(p);
	}
}

void addX(int x , piii u){
	while(Sx[x].size() && Sx[x].front().F.S <= u.F.S) Sx[x].pop_front();
	if(Sx[x].size() && Sx[x].front().F.F <= u.F.S){
		Sx[x].front().F.F = in[adj[rinv[u.F.S]][0]];
	}
	while(Sx[x].size() && Sx[x].front().S == u.S){
		u.F.S = Sx[x].front().F.S;
		Sx[x].pop_front();
	}
	Sx[x].push_front(u);
}

set<int> compress;
map<int,int> poscompress;
int vc = 0;

int bit[N + 100];

int get(int x){
	int s = 0;
	for(int i = x ; i > 0 ; i-=(i&-i)) s+= bit[i];
	return s;
}

void add(int x , int vl){
	for(int i = x ; i < N + 100 ; i+=(i&-i)) bit[i] += vl;
}

int32_t main(){
	scanf("%d" , &n);
	for(int i = 1 ; i <= n; i++) scanf("%d" ,&C[i]) , compress.insert(C[i]);
	for(auto p : compress){
		poscompress[p] = ++vc;
	}
	for(int i = 1 ; i <= n; i ++) C[i] = poscompress[C[i]];
	for(int i = 1 ; i < n ; i ++){
		int x, y;
		scanf("%d%d" , &x , &y);
		adj[x].pb(y);
		adj[y].pb(x);
		edge.push_back(pii(x,y));
	}
	dfs(1,1);
	dfs_hld(1,1);
	addX(ch[1] , piii(pii(in[1] , in[1]) , C[1]));
	for(auto p : edge){
		elements.clear();
		int X = p.F;
		while(X != -1){
			getX(X);
			X = pai[ch[X]];
		}
		X = p.S;
		while(X != -1){
			addX(ch[X] , piii(pii(in[ch[X]] , in[X]), C[p.S]));
			X = pai[ch[X]];
		}
		reverse(elements.begin() , elements.end());
		long long ans = 0;
		for(auto p : elements){
			add(p.F, p.S);
			long long U = get(N + 90) - get(p.F);
			U *= (1LL)*((long long)p.S);
			ans += U; 
		}
		for(auto p : elements){
			add(p.F , -p.S);
		}
		printf("%lld\n" , ans);
	}
}

Compilation message (stderr)

construction.cpp: In function 'int32_t main()':
construction.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
  ~~~~~^~~~~~~~~~~
construction.cpp:87:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1 ; i <= n; i++) scanf("%d" ,&C[i]) , compress.insert(C[i]);
                               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~

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