QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#293771	#7855. 不跳棋	JWRuixi	60	675ms	192880kb	C++17	4.1kb	2023-12-29 18:49:41	2023-12-29 18:49:42

Judging History

你现在查看的是最新测评结果

[2023-12-29 18:49:42]
评测

测评结果：60
用时：675ms
内存：192880kb

查看

[2023-12-29 18:49:41]
提交

answer

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
// #define ATC
#define IL inline
#define LL long long
#define eb emplace_back
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FIO(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
using namespace std;

#ifdef ATC
#include <atcoder/all>
using namespace atcoder;
#endif

namespace IO {
	char ibuf[1 << 20], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 20, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
	inline long long read() {
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}
	template<typename _Tp>
	inline void write(_Tp x) {
		static char stk[64], *top = stk;
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		do *top++ = x % 10, x /= 10;
		while (x);
		while (top != stk) putchar((*--top) | 48);
	}
}

using IO::read;
using IO::write;

using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define MP make_pair

constexpr int N = 5e5 + 9, INF = 1e9 + 7;
int n, typ, sz[N], son[N];
vector<int> G[N];

struct vNode {
	int v;
	LL c;
	vNode (int v = INF, LL c = 0) : v(v), c(c) {}
	vNode operator + (const vNode &z) const {
		return v < z.v ? *this : v > z.v ? z : vNode(v, c + z.c);
	}
	vNode& operator += (const vNode &z) {
		return *this = *this + z;
	}
};

/**
 * Cluster
 * x : upper
 * y : lower
 * all : dis(x, y)
 * v : min length
 * u : min length to x
 * d : min length to y
*/

struct cNode {
	enum {I, C, R} typ = I;
	int x, y, all;
	vNode v, u, d;
};

cNode C (const cNode &a, const cNode &b) {
	cNode c;
	c.typ = cNode::C;
	c.x = a.x, c.y = b.y;
	c.all = a.all + b.all;
	c.u = a.u + vNode(a.all + b.u.v, b.u.c);
	c.d = b.d + vNode(b.all + a.d.v, a.d.c);
	c.v = a.v + b.v + vNode(a.d.v + b.u.v, a.d.c * b.u.c);
	return c;
}

cNode R (const cNode &a, const cNode &b) {
	cNode c;
	c.typ = cNode::R;
	c.x = a.x, c.y = a.y;
	c.all = a.all;
	c.u = a.u + b.u;
	c.d = a.d + vNode(a.all + b.u.v, b.u.c);
	c.v = a.v + b.v + vNode(a.u.v + b.u.v, a.u.c * b.u.c);
	return c;
}

#define ls(p) tr[p].lc
#define rs(p) tr[p].rc

int rt, tot;

struct TNode {
	int lc, rc, p, sz;
	cNode v;
} tr[N << 2];

IL void dfs1 (int u, int fa) {
	sz[u] = 1;
	tr[u].v = cNode{cNode::I, fa, u, 1, vNode(), vNode(1, 1), vNode(0, 1)};
	if (u > 1) {
		G[u].erase(find(G[u].begin(), G[u].end(), fa));
	}
	for (int v : G[u]) {
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

IL int bld (vi::iterator L, vi::iterator R, auto F) {
	if (L == R - 1) {
		return *L;
	}
	int all = 0;
	for (auto i = L; i != R; ++i) {
		all += tr[*i].sz;
	}
	vi::iterator mid = L + 1;
	int sum = 0;
	for (auto i = L; i != R; ++i) {
		sum += tr[*i].sz;
		if (sum > all / 2) {
			mid = i;
			break;
		}
	}
	int x = bld(L, mid, F), y = bld(mid, R, F);
	++tot;
	ls(tot) = x, rs(tot) = y;
	tr[x].p = tot, tr[y].p = tot;
	tr[tot].sz = tr[x].sz + tr[y].sz;
	tr[tot].v = F(tr[x].v, tr[y].v);
	return tot;
}

IL int dfs2 (int u) {
	vi vc{u};
	for (int p = u; son[p]; p = son[p]) {
		vi ve{son[p]};
		for (int v : G[p]) {
			if (v != son[p]) {
				ve.eb(dfs2(v));
			}
		}
		vc.eb(bld(ve.begin(), ve.end(), R));
	}
	return bld(vc.begin(), vc.end(), C);
}

int main() {
	n = read(), typ = read();
	for (int i = 1, u, v; i < n; i++) {
		u = read(), v = read();
		G[u].eb(v);
		G[v].eb(u);
	}
	dfs1(1, 0);
	tot = n, rt = dfs2(1);
	int as = 0;
	for (int i = 1; i < n - 1; i++) {
		int u = read();
		if (typ) {
			u ^= as;
		}
		tr[u].v.v = tr[u].v.u = tr[u].v.d = vNode();
		for (u = tr[u].p; u; u = tr[u].p) {
			tr[u].v = (tr[u].v.typ == cNode::C ? C : R)(tr[ls(u)].v, tr[rs(u)].v);
		}
		writesp(tr[rt].v.v.v), writeln(as = tr[rt].v.v.c);
	}
}
// I love WHQ!

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4

Accepted

time: 32ms

memory: 172368kb

input:

output:

result:

ok 98 lines

Test #2:

score: 4

Accepted

time: 12ms

memory: 173188kb

input:

output:

result:

ok 98 lines

Test #3:

score: 4

Accepted

time: 11ms

memory: 173924kb

input:

output:

result:

ok 98 lines

Test #4:

score: 4

Accepted

time: 15ms

memory: 174136kb

input:

output:

result:

ok 998 lines

Test #5:

score: 4

Accepted

time: 21ms

memory: 174300kb

input:

output:

result:

ok 998 lines

Test #6:

score: 4

Accepted

time: 19ms

memory: 172144kb

input:

output:

result:

ok 998 lines

Test #7:

score: 4

Accepted

time: 200ms

memory: 181168kb

input:

output:

result:

ok 199998 lines

Test #8:

score: 4

Accepted

time: 245ms

memory: 180624kb

input:

output:

result:

ok 199998 lines

Test #9:

score: 4

Accepted

time: 217ms

memory: 181816kb

input:

output:

result:

ok 199998 lines

Test #10:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #11:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #13:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #14:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #15:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #16:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #17:

score: 4

Accepted

time: 209ms

memory: 181776kb

input:

output:

result:

ok 199998 lines

Test #18:

score: 4

Accepted

time: 241ms

memory: 181868kb

input:

output:

result:

ok 199998 lines

Test #19:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #20:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #21:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #22:

score: 4

Accepted

time: 658ms

memory: 192632kb

input:

output:

result:

ok 499998 lines

Test #23:

score: 4

Accepted

time: 675ms

memory: 192880kb

input:

output:

result:

ok 499998 lines

Test #24:

score: 4

Accepted

time: 644ms

memory: 192588kb

input:

output:

result:

ok 499998 lines

Test #25:

score: 4

Accepted

time: 658ms

memory: 192832kb

input:

output:

result:

ok 499998 lines