QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#661732#8551. DFS Order 5LeNcyerWA 2ms9904kbC++174.2kb2024-10-20 17:49:162024-10-20 17:49:17

Judging History

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

  • [2024-10-20 17:49:17]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9904kb
  • [2024-10-20 17:49:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
using ll = long long;

const int N = 1e5 + 10;
const int lim = 20;

class Segment{
private:
	struct Node {
		int val, tag;
	} node[N << 2];
public:
	void push_up (int p) {
		node[p].val = node[p << 1].val | node[p << 1 | 1].val;
	}
	void build (int s, int t, int p = 1) {
		node[p].tag = -1;
		if (s == t) {
			node[p].val = 0;
			return;
		}
		int mid = (s + t) >> 1;
		build(s, mid, p << 1);
		build(mid + 1, t, p << 1 | 1);
		push_up(p);
	}
	void push_down (int p) {
		if (node[p].tag != -1) {
			node[p << 1].tag = node[p << 1].val = node[p].tag;
			node[p << 1 | 1].tag = node[p << 1 | 1].val = node[p].tag;			
			node[p].tag = -1;
		}
	}
	void update (int l, int r, int v, int s, int t, int p = 1) {
		if (l <= s && t <= r) {
			node[p].val = v;
			node[p].tag = v;
			return;
		}
		push_down(p);
		int mid = (s + t) >> 1;
		if (l <= mid) update(l, r, v, s, mid, p << 1);
		if (mid < r) update(l, r, v, mid + 1, t, p << 1 | 1);
		push_up(p);
	}
	int query (int l, int r, int s, int t, int p = 1) {
		if (l <= s && t <= r) return node[p].val;
		push_down(p);
		int mid = (s + t) >> 1;
		int res = 0;
		if (l <= mid) res = query(l, r, s, mid, p << 1);
		if (mid < r) res |= query(l, r, mid + 1, t, p << 1 | 1);
		push_up(p);
		return res;
	}
};
Segment seg;

int n, q;
vector<int> t[N];
int dep[N], f[N][lim];
int sz[N], dfn[N], hs[N], tp[N], totdfn = 0;

void dfs (int x, int fa) {
	f[x][0] = fa;
	dep[x] = dep[fa] + 1;
	sz[x] = 1;
	for (int i = 1; i < lim; i ++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	hs[x] = 0;
	for (auto y: t[x]) {
		if (y == fa) continue;
		dfs(y, x);
		sz[x] += sz[y];
		if(sz[y] > sz[hs[x]]) hs[x] = y;
	}
}

void dfs2 (int x, int fa, int top) {
	dfn[x] = ++ totdfn;
	tp[x] = top;
	if (hs[x]) dfs2(hs[x], x, top);
	for (auto y: t[x]) {
		if (y == fa || y == hs[x]) continue;
		dfs2(y, x, y);
	}
}

int get (int x, int len) {
	int cur = x;
	for (int i = 0; i < lim; i ++) {
		if ((len >> i) & 1) cur = f[cur][i];
	}
	return cur;
}

int get_lca (int x, int y) {
	for (int i = lim - 1; i >= 0; i --) {
		if (dep[f[x][i]] >= dep[y]) x = f[x][i];
		if (dep[f[y][i]] >= dep[x]) y = f[y][i];
	}
	if (x == y) return x;
	for (int i = lim - 1; i >= 0; i --) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}

int cal (int x, int y) {
//	cout << "cal: " << x << ' ' << y << endl;
	int res = 0;
	while (dep[x] >= dep[y]) {
		int l = dfn[tp[x]], r = dfn[x];
		if (dep[y] > dep[tp[x]]) l = dfn[y];
		res |= seg.query(l, r, 1, n);
		if (res) return res;
		x = f[tp[x]][0];
	}
	return res;
}
void col (int x, int y) {
	while (dep[x] >= dep[y]) {
		int l = dfn[tp[x]], r = dfn[x];
		if (dep[y] > dep[tp[x]]) l = dfn[y];
		seg.update(l, r, 1, 1, n);
		x = f[tp[x]][0];
	}
	return;
}

void init () {
	cin >> n >> q;
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		t[u].push_back(v);
		t[v].push_back(u);
	}
}

int a[N], pos[N];

void solve() {
	init();
	dfs(1, 0);
	dfs2(1, 0, 1);
	seg.build(1, n);
	
//	for (int i = 1; i <= n; i ++) {
//		cout << i << ' ' << hs[i] << ' ' << tp[i] << endl;
//	}
//    cout << "debug\n";
	for (int _ = 1; _ <= q; _ ++) {
		int k;
		cin >> k;
		for (int i = 1; i <= k; i ++) {
			cin >> a[i];
			pos[a[i]] = i;
		}
		
		if (_ == 30) {
			cout << k << ':';
			for (int i = 1; i <= k; i ++) cout << a[i] << ',';
			return;
		}
		
		seg.update(1, n, 0, 1, n);
		bool ok = 1;
		for (int i = 2; i <= k; i ++) {
			int r = min(k, i + sz[a[i]] - 1);
			if (get_lca(a[i], a[r]) != a[i]) {
				ok = 0;
				break;
			}
			int fa = f[a[i]][0];
			if (fa == a[i - 1]) continue;
			
			int lca = get_lca(a[i - 1], a[i]);
			if (fa != lca) {
				ok = 0;
				break;
			}
			int u = a[i - 1], v = get(a[i - 1], dep[a[i - 1]] - dep[fa] - 1);
			if (cal(u, v) || cal(a[i], a[i])) {
				ok = 0;
				break;
			}
			col(u, v);
		}
		if (ok) cout << "Yes\n";
		else cout << "No\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _ = 1;
//    cin >> _;
	while (_--)
		solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9904kb

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

No
No
Yes
No
No
Yes
Yes

result:

ok 7 tokens

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 9804kb

input:

10 100000
7 2
1 7
7 10
8 6
8 7
1 3
4 5
9 5
5 8
8 8 9 7 2 8 1 6 1
4 8 3 5 2
6 7 10 3 9 9 1
1 1
8 10 3 2 9 3 8 7 3
7 5 6 2 8 5 9 1
6 3 4 6 2 1 3
5 8 9 2 4 9
1 3
2 1 5
5 8 5 1 7 9
10 5 2 9 2 6 4 10 6 3 8
3 4 5 8
2 8 4
9 4 10 1 2 4 3 3 6 3
1 3
6 1 1 6 8 3 1
3 7 3 2
3 9 1 5
4 3 7 8 10
9 4 2 3 10 2 5 4 3 ...

output:

No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
3:5,6,10,

result:

wrong answer 30th words differ - expected: 'No', found: '3:5,6,10,'