제출 #62803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62803		kingpig9	Construction of Highway (JOI18_construction)	C++11	16 / 100	2074 ms	42376 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) {
		debug("update %d, (%d, %d)\n", x, v.fi, v.se);
		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
	//debug("x = %d. query [%d, %d)\n", x, ent[x], exi[x]);
	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);
	}
	//debug("updpath(%d)\n", x);
	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;
	}
	for (int i = 0; i < 2; i++) {
		if (n == n->p->ch[i]) {
			return i;
		}
	}
	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 push (node *n) {
	//nothing
}

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...
#warning is this correct (in rot function)?
	setc(n, p, !d);
	pull(p);
	pull(n);
}

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

vector<pii> expose (node *u) {
	//pii(size, value of node)
	debug("----------------expose %d-------------------\n", u->id);
	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);
		debug("id = %d, lastupd = %d. Size = %d\n", cur->id, lastupd(cur->id), cur->size - psize);
		if (v != null) {
			res.push_back(pii(lastupd(cur->id), cur->size - psize));
		}
		psize = cur->size;
	}
	splay(u);

	/*
	for (pii p : res) {
		debug("(%d, %d) ", p.fi, p.se);
	}
	debug("\n");
	*/

	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();
		debug("C[%d] = %d\n", i, C[i]);
	}
	
	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];
	}

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

		updpath(b);
		debug("--------SATAN 2-------------\n");
	}
}

컴파일 시 표준 에러 (stderr) 메시지

construction.cpp:117:2: warning: #warning is this correct (in rot function)? [-Wcpp]
 #warning is this correct (in rot function)?
  ^~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:224:7: warning: unused variable 'a' [-Wunused-variable]
   int a = A[i], b = B[i];
       ^
construction.cpp:187:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
construction.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~
construction.cpp:201: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: 0 / 84