Submission #62902

#	Time	Username	Problem	Language	Result	Execution time	Memory
62902		kingpig9	Construction of Highway (JOI18_construction)	C++11	100 / 100	1792 ms	19756 KiB

construction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 17;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
int A[MAXN], B[MAXN];
int C[MAXN];
vector<int> adj[MAXN];
int ent[MAXN], exi[MAXN];

struct segtree {
	pii tree[2 * MAXN];	//pii(time, value)

	void update (int x, pii v) {
		tree[x += MAXN] = v;
		while (x >>= 1) {
			tree[x] = max(tree[2 * x], tree[2 * x + 1]);
		}
	}

	pii query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
		if (rt <= a || b <= lt) {
			return pii(-1, -1);
		}

		if (a <= lt && rt <= b) {
			return tree[cur];
		}

		int mid = (lt + rt) / 2;
		return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
	}
} seg;

void updpath (int x) {
	static int updtime = 0;
	seg.update(ent[x], pii(++updtime, C[x]));
}

int lastupd (int x) {
	//last update of this one
	return seg.query(ent[x], exi[x]).se;
}

void dfs (int x) {
	static int cur = 0;
	ent[x] = cur++;
	for (int y : adj[x]) {
		dfs(y);
	}
	exi[x] = cur;
	updpath(x);
	assert(lastupd(x) == C[x]);
}

struct node {
	node *ch[2], *p;
	int id;
	int size;
} *null = new node, nodes[MAXN];

int getdir (node *n) {
	if (n->p == null) {
		return -1;
	}
	if (n == n->p->ch[0]) {
		return 0;
	}
	if (n == n->p->ch[1]) {
		return 1;
	}
	return -1;
}

bool isroot (node *n) {
	return getdir(n) == -1;
}

void setc (node *n, node *c, int d) {
	n->ch[d] = c;
	if (c != null) {
		c->p = n;
	}
}

void pull (node *n) {
	n->size = n->ch[0]->size + 1 + n->ch[1]->size;
}

void rot (node *n) {
	node *p = n->p, *g = p->p;
	bool d = getdir(n);
	//note that this matters in an LCT. cannot cal setc on g and n
	if (!isroot(p)) {
		g->ch[getdir(p)] = n;
	}
	setc(p, n->ch[!d], d);
	n->p = g;	//this line forgot include...
	setc(n, p, !d);
	pull(p);
	pull(n);
}

void splay (node *n) {
	while (!isroot(n)) {
		node *p = n->p;
		if (!isroot(p)) {
			rot(getdir(n) == getdir(p) ? p : n);
		}
		rot(n);
	}
}

vector<pii> expose (node *u) {
	//pii(size, value of node)
	vector<pii> res;
	int psize = 0;

	for (node *cur = u, *v = null; cur != null; v = cur, cur = cur->p) {
		splay(cur);
		assert(v == null || v->p == cur);
		cur->ch[1] = v;
		pull(cur);
		if (v != null) {
			res.push_back(pii(lastupd(cur->id), cur->size - psize));
		}
		psize = cur->size;
	}
	splay(u);

	return res;
}

struct fenwick {
	ll bit[MAXN];

	void update (int x, ll v) {
		for (x++; x < MAXN; x += (x & -x)) {
			bit[x] += v;
		}
	}

	ll query (int x) {
		ll res = 0;
		for (x++; x; x &= (x - 1)) {
			res += bit[x];
		}
		return res;
	}
} fen;

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &C[i]);
	}
	//compress C
	vector<int> vals(C, C + N);
	sort(all(vals));
	vals.resize(unique(all(vals)) - vals.begin());
	for (int i = 0; i < N; i++) {
		C[i] = lower_bound(all(vals), C[i]) - vals.begin();
	}
	
	for (int i = 0; i < N - 1; i++) {
		scanf("%d %d", &A[i], &B[i]);
		A[i]--;
		B[i]--;
		adj[A[i]].push_back(B[i]);
	}

	dfs(0);

	//NOW THE NODES!
	null->ch[0] = null->ch[1] = null->p = null;
	null->id = -1073741819;
	null->size = 0;
	for (int i = 0; i < N; i++) {
		nodes[i].ch[0] = nodes[i].ch[1] = nodes[i].p = null;
		nodes[i].id = i;
		nodes[i].size = 1;
	}

	for (int i = 0; i < N - 1; i++) {
		nodes[B[i]].p = nodes + A[i];
	}

	int sumsz = 0;
	for (int i = 0; i < N - 1; i++) {
		int b = B[i];
		vector<pii> v = expose(nodes + b);
		//we want the number of strictly less than this value.
		ll ans = 0;
		sumsz += v.size();
		for (pii p : v) {
			ans += p.se * fen.query(p.fi - 1);
			fen.update(p.fi, p.se);
		}
		for (pii p : v) {
			fen.update(p.fi, -p.se);
		}
		printf("%lld\n", ans);

		updpath(b);
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:165:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
construction.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~
construction.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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