Submission #82494

#	Time	Username	Problem	Language	Result	Execution time	Memory
82494		wzy	Construction of Highway (JOI18_construction)	C++11	0 / 100	2048 ms	14932 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int N = 100005; 
int sz[N] , in[N] , out[N] , C[N], t = 0 , ch[N] , depth[N] , inv[N] , pai[N] , endch[N];
vector<int> adj[N];
int n;
vector<pii> edge;
void dfs(int x , int y){
	sz[x] = 1;
	depth[x] = 0;
	depth[x] = depth[y] + 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[p] >= sz[adj[x][0]]) swap(p, adj[x][0]);
	}
}

int dfs_hld(int x, int y){
	in[x] = ++t;
	inv[in[x]] = x;
	endch[ch[x]] = 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);
	}
	out[x] = t;
}
class ST{
public: 
void init(int r ){
	st.resize(5*100105);
	lazy.resize(5*100105);
}

void propaga(int l, int r , int curr){
	if(lazy[curr]){
		st[curr] = lazy[curr];
		if(l!=r) lazy[2*curr] = lazy[curr] , lazy[2*curr + 1] = lazy[curr];
		lazy[curr] = 0;
		return ;
	}
}

void update(int x , int y , int vl , int l = 1 , int r = 100105 , int curr = 1){
	int mid = (l+r)/2;
	if(x == l && y == r){
		lazy[curr] = vl;
		return ;
	}
	if(y <= mid) update(x,y,vl,l,mid,2*curr);
	else if(x > mid) update(x,y,vl,mid+1,r,2*curr +1);
	else{
		update(x,mid,vl,l,mid,2*curr);
		update(mid+1,y,vl,mid+1,r,2*curr+1);
	}
}

int query(int x  , int l = 1 , int r = 100105, int curr = 1){
	int mid = (l+r)/2;
	propaga(l,r,curr);
	if(x == l && l == r){
		return st[curr];
	}
	if(x <= mid) return query(x,l,mid , 2*curr);
	return query(x,mid+1,r,2*curr + 1);
}
private : 
vector<int> st , lazy ;
};

ST A , B, D;


map<int,int> ordi;
set<int> sorti;

int BIT[N + 100];

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

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


int32_t main(){
	scanf("%d" , &n);
	for(int i = 1 ; i <= n; i ++) scanf("%d" , &C[i]) , sorti.insert(C[i]);
	int CC = 0;
	for(auto p : sorti){
		ordi[p] = ++CC;
	}
	for(int i = 1 ; i <= n; i ++){
		C[i] = ordi[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));
	}
	A.init(n + 10 ) , B.init(n + 10) , D.init(n + 10);
	ch[1] = 1;
	dfs(1,1);
	dfs_hld(1,1);
	B.update(in[1] , in[1] , 1);
	A.update(in[1] , in[1] , C[1]);
	D.update(in[1] , in[1] , 1);
	ch[1] = 1 , pai[1] = -1;
	int cnt = 0;
	for(auto p : edge){
		int L = p.F , R = p.F;
		vector<pii> q;
		while(L != -1 && R != -1){
			L = B.query(in[R]);
			q.push_back(pii(A.query(in[R]) , depth[R] - depth[L] + 1));
			R = pai[L];
		}
		reverse(q.begin() , q.end());
		long long ans = 0;
		for(auto w : q){
			add(w.F , w.S);
			int U = get(CC + 2) - get(w.F);
			long long P = U;
			P *= w.S;
			ans += P;
		}
		for(auto w : q){
			add(w.F , -w.S);
		}
		printf("%lld\n" , ans);
		cnt++;
		L = ch[p.S] , R = p.S;
		while(L != -1 && R != -1){
			if(adj[R][0] != pai[R] && C[p.S] != A.query(in[adj[R][0]]) && R != p.S && D.query(adj[R][0]) > 0){
				// olha o end de cada chain
				B.update(in[adj[R][0]] , in[D.query(in[adj[R][0]])] , adj[R][0]);
			}
			B.update(in[L] , in[R] , L);
			A.update(in[L], in[R] , C[p.S]);
			D.update(in[L] , in[R] , R);
			R = pai[L];
			L = ch[R];
		}
	}

}
/* 
10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10
*/

Compilation message (stderr)

construction.cpp: In function 'int dfs_hld(int, int)':
construction.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
construction.cpp: In function 'int32_t main()':
construction.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
  ~~~~~^~~~~~~~~~~
construction.cpp:105:52: 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]) , sorti.insert(C[i]);
                                ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:115: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: 0 / 7
• Subtask 2: 0 / 9
• Subtask 3: 0 / 84