oj.uz

Submission #649819

# Submission time Handle Problem Language Result Execution time Memory
649819 2022-10-11T11:14:13 Z ymm Construction of Highway (JOI18_construction) C++17
0 / 100
 2 ms 340 KB 
#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)
{
	assert(v->p);
	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;
}

int assert_cnt(node *v)
{
	if (!v)
		return 0;
	return 1 + assert_cnt(v->c[0]) + assert_cnt (v->c[1]);
}

vector<pii> access(node *v)
{
	splay(v);
	detach_right(v);
	assert(v->cnt == assert_cnt(v));
	vector<pii> ans = {{v->cnt, v->live}};
	while (v->path_par) {
		node *u = v->path_par;
		splay(u);
		detach_right(u);
		assert(u->cnt == assert_cnt(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;
	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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Halted 0 ms 0 KB -