Submission #649795

#	Time	Username	Problem	Language	Result	Execution time	Memory
649795		ymm	Construction of Highway (JOI18_construction)	C++17	0 / 100	2 ms	468 KiB

construction

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

struct node {
	node *path_par;
	node *p;
	node *c[2];
	int live;
	int cnt;
};

bool side(node *v)
{
	return v->p->c[1] == v;
}

void rot(node *v)
{
	assert(v->p);
	node *p = v->p;
	bool s = side(v);
	if (p->p)
		p->p->c[side(p)] = v;
	v->p = p->p;
	if (v->c[!s])
		v->c[!s]->p = p;
	p->c[s] = v->c[!s];
	v->c[!s] = p;
	p->p = v;
	p->cnt -= v->c[s]? 1 + v->c[s]->cnt: 1;
	v->cnt += p->c[!s]? 1 + p->c[!s]->cnt: 1;
	v->live = p->live;
	v->path_par = p->path_par;
}

void splay(node *v)
{
	while (v->p && v->p->p) {
		side(v) == side(v->p)? rot(v->p): rot(v);
		rot(v);
	}
	if (v->p)
		rot(v);
}

void attach_right(node *v, node *r)
{
	assert(!v->c[1]);
	assert(!r->p);
	v->c[1] = r;
	r->p = v;
	v->cnt += r->cnt;
}

void detach_right(node *v)
{
	if (v->c[1]) {
		v->c[1]->p = 0;
		v->c[1]->path_par = v;
		v->cnt -= v->c[1]->cnt;
	}
	v->c[1] = 0;
}

vector<pii> access(node *v)
{
	splay(v);
	detach_right(v);
	vector<pii> ans = {{v->cnt, v->live}};
	while (v->path_par) {
		node *u = v->path_par;
		splay(u);
		detach_right(u);
		ans.push_back({u->cnt, u->live});
		attach_right(u, v);
		splay(v);
	}
	return ans;
}

void link(node *v, node *u)
{
	assert(!v->p && !v->path_par);
	assert(!u->p && !u->path_par && !u->c[0]);
	u->path_par = v->path_par;
	u->cnt += v->cnt;
	u->c[0] = v;
	v->p = u;
	// live will automatically be ok
}

const int N = 100'010;
node nd[N];
int n;

int fen[N];
int fen_get(int r)
{
	int ans = 0;
	while (r > 0) {
		ans += fen[r];
		r -= r & -r;
	}
	return ans;
}
void fen_add(int i, int x)
{
	++i;
	while (i <= n) {
		fen[i] += x;
		i += i & -i;
	}
}

vector<int *> cmper;
void compress()
{
	sort(cmper.begin(),cmper.end(), [](int *x, int *y){return *x<*y;});
	int cnt = 0;
	Loop (i,0,cmper.size()) {
		if (i && *cmper[i-1] != *cmper[i])
			++cnt;
		*cmper[i] = cnt;
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	vector<int *> cmper;
	Loop (i,0,n) {
		cin >> nd[i].live;
		nd[i].cnt = 1;
		cmper.push_back(&nd[i].live);
	}
	compress();
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		auto tmp = access(&nd[v]);
		link(&nd[v], &nd[u]);
		ll ans = 0;
		for (auto [cnt, x] : tmp) {
			ans += (ll)fen_get(x) * cnt;
			fen_add(x, cnt);
		}
		for (auto [cnt, x] : tmp)
			fen_add(x, -cnt);
		cout << ans << '\n';
	}
}

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