Submission #1073075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073075		rainboy	Telephone Plans (CCO24_day2problem3)	C11	25 / 25	1472 ms	73108 KiB

Main

#include <stdio.h>

#define N	500000
#define Q	1500000

int tt[N + 1][2], pp[N + 1], sz[N + 1], sz_[N + 1]; char lz[N + 1];

int dir(int u) {
	return tt[pp[u]][0] == u ? 0 : 1;
}

int is_root(int u) {
	return tt[pp[u]][dir(u)] != u;
}

void put(int u) {
	if (u) {
		int tmp;

		tmp = tt[u][0], tt[u][0] = tt[u][1], tt[u][1] = tmp;
		lz[u] ^= 1;
	}
}

void pus(int u) {
	if (lz[u])
		put(tt[u][0]), put(tt[u][1]), lz[u] = 0;
}

void pul(int u) {
	sz[u] = sz[tt[u][0]] + sz_[u] + sz[tt[u][1]];
}

void attach(int u, int v, int d) {
	if (u)
		tt[u][d] = v, pul(u);
	if (v)
		pp[v] = u;
}

void rotate(int u) {
	int v, w, du, dv, isrt;

	v = pp[u], w = pp[v];
	pus(w), pus(v), pus(u);
	du = dir(u), dv = dir(v), isrt = is_root(v);
	attach(v, tt[u][du ^ 1], du);
	attach(u, v, du ^ 1);
	if (isrt)
		pp[u] = w;
	else
		attach(w, u, dv);
}

void splay(int u) {
	while (!is_root(u)) {
		int v = pp[u];

		if (!is_root(v))
			pus(v), rotate(dir(u) == dir(v) ? v : u);
		rotate(u);
	}
	pus(u);
}

void expose(int u) {
	int v, w;

	for (v = u, w = 0; v; w = v, v = pp[v]) {
		splay(v);
		sz_[v] += sz[tt[v][1]], attach(v, w, 1), sz_[v] -= sz[w];
		pul(v);
	}
	splay(u), put(u), pus(u);
}

long long m;

void link(int u, int v) {
	expose(u), expose(v);
	m += (long long) sz[u] * sz[v];
	sz_[u] += sz[tt[u][1]], attach(u, v, 1), pul(u);
}

void cut(int u, int v) {
	expose(u), expose(v);
	m -= (long long) sz_[v] * (sz[v] - sz_[v]);
	attach(v, 0, 1), pp[u] = 0;
}

int main() {
	static long long mm[Q + 1], ss[Q + 1];
	int n, q, h, encrypted, i, j, d, t;
	long long i_, j_, d_, ans;

	scanf("%d%d%d", &encrypted, &n, &q);
	for (i = 1; i <= n; i++)
		sz_[i] = 1;
	mm[0] = 0;
	ans = 0;
	for (h = 1; h <= q; h++) {
		scanf("%d", &t);
		if (t == 1) {
			scanf("%lld%lld", &i_, &j_);
			if (!encrypted)
				i = i_, j = j_;
			else
				i = i_ ^ ans, j = j_ ^ ans;
			link(i, j);
			mm[h] = m, ss[h] = ss[h - 1];
		} else if (t == 2) {
			scanf("%lld%lld", &i_, &j_);
			if (!encrypted)
				i = i_, j = j_;
			else
				i = i_ ^ ans, j = j_ ^ ans;
			cut(i, j);
			mm[h] = m, ss[h] = ss[h - 1] + mm[h - 1] - mm[h];
		} else {
			scanf("%lld", &d_);
			if (!encrypted)
				d = d_;
			else
				d = d_ ^ ans;
			mm[h] = m, ss[h] = ss[h - 1];
			printf("%lld\n", ans = mm[h] + ss[h] - ss[h - d]);
		}
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d%d%d", &encrypted, &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:102:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
Main.c:104:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |    scanf("%lld%lld", &i_, &j_);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:112:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |    scanf("%lld%lld", &i_, &j_);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:120:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |    scanf("%lld", &d_);
      |    ^~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 2 / 2
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5