This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, ans;
long long i_, j_, d_;
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("%d\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_);
| ^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |