제출 #373764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373764		lohacho	Construction of Highway (JOI18_construction)	C++14	100 / 100	795 ms	22636 KiB

construction

#include <bits/stdc++.h>

using namespace std;

const int NS = (int)1e5 + 4;
int n, c[NS];
vector<int> way[NS];
int sz[NS], in[NS], incnt, up[NS], pr[NS];
pair<int, int> que[NS];
vector<pair<int, int>> block;

void dfs_sz(int x, int from){
	sz[x] = 1; pr[x] = from;
	for(auto&nxt:way[x]){
		if(nxt == from){
			continue;
		}
		dfs_sz(nxt, x);
		sz[x] += sz[nxt];
		if(way[x][0] == from || sz[way[x][0]] < sz[nxt]){
			swap(way[x][0], nxt);
		}
	}
}

void dfs_hld(int x, int from){
	in[x] = incnt++;
	for(auto&nxt:way[x]){
		if(nxt == from){
			continue;
		}
		if(way[x][0] == nxt){
			up[nxt] = up[x];
		}
		else{
			up[nxt] = nxt;
		}
		dfs_hld(nxt, x);
	}
}

struct Seg{
	int n;
	vector<int> tree, lazy;
	Seg(int N):n(N){
		tree.resize(n * 4, -1), lazy.resize(n * 4, -1);
	}
	void add(int x, int l, int r, int val){
		lazy[x] = val;
		tree[x] = val;
	}
	void update(int x, int l, int r){
		if(lazy[x] == -1) return;
		int mid = (l + r) >> 1;
		add(x * 2, l, mid, lazy[x]), add(x * 2 + 1, mid + 1, r, lazy[x]);
		lazy[x] = -1;
	}
	void push(int x, int l, int r, int pl, int pr, int val){
		if(pr < l || pl > r || pl > pr) return;
		if(l >= pl && r <= pr){
			add(x, l, r, val);
			return;
		}
		update(x, l, r);
		int mid = (l + r) >> 1;
		push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val);
		if(tree[x * 2] == tree[x * 2 + 1] && tree[x * 2] != -1){
			tree[x] = tree[x * 2];
		}
		else{
			tree[x] = -1;
		}
	}
	void get(int x, int l, int r, int fl, int fr){
		if(fr < l || fl > r || fl > fr) return;
		if(tree[x] != -1){
			block.push_back({tree[x], min(r, fr) - max(l, fl) + 1});
			return;
		}
		update(x, l, r);
		int mid = (l + r) >> 1;
		get(x * 2 + 1, mid + 1, r, fl, fr);
		get(x * 2, l, mid, fl, fr);
	}
};

struct Fenwick{
	int n;
	vector<int> tree;
	Fenwick(int N):n(N){
		tree.resize(n);
	}
	void push(int x, int y){
		for(int i = x; i < n; i |= i + 1) tree[i] += y;
	}
	int get(int x){
		int rv = 0;
		for(int i = x; i >= 0; i = (i & (i + 1)) - 1){
			rv += tree[i];
		}
		return rv;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	vector<int> srt;
	for(int i = 0; i < n; ++i){
		cin >> c[i];
		srt.push_back(c[i]);
	}
	sort(srt.begin(), srt.end());
	srt.erase(unique(srt.begin(), srt.end()), srt.end());
	for(int i = 0; i < n; ++i){
		c[i] = lower_bound(srt.begin(), srt.end(), c[i]) - srt.begin();
	}
	for(int i = 0; i < n - 1; ++i){
		int x, y; cin >> x >> y; --x, --y;
		que[i] = {x, y};
		way[x].push_back(y), way[y].push_back(x);
	}
	dfs_sz(0, -1);
	dfs_hld(0, -1);
	Seg seg(n + 4);
	seg.push(1, 0, n - 1, 0, 0, c[0]);
	Fenwick sum(n + 4);
	for(int i = 0; i < n - 1; ++i){
		int x = que[i].first;
		while(x != -1){
			seg.get(1, 0, n - 1, in[up[x]], in[x]);
			x = pr[up[x]];
		}
		vector<pair<int, int>> col;
		for(auto&i:block){
			if((int)col.size() && col.back().first == i.first){
				col.back().second += i.second;
			}
			else{
				col.push_back({i.first, i.second});
			}
		}
		block.clear();
		long long ans = 0;
		for(auto&i:col){
			ans += (long long)sum.get(i.first - 1) * i.second;
			sum.push(i.first, i.second);
		}
		for(auto&i:col){
			sum.push(i.first, -i.second);
		}
		cout << ans << '\n';
		x = que[i].second;
		while(x != -1){
			seg.push(1, 0, n - 1, in[up[x]], in[x], c[que[i].second]);
			x = pr[up[x]];
		}
	}
	return 0;
}

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