QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417529#8716. 树fallleaves01#WA 0ms3616kbC++201.5kb2024-05-22 19:34:132024-05-22 19:34:13

Judging History

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

  • [2024-05-22 19:34:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2024-05-22 19:34:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<int>> e(n + 1);
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	vector<int> dep(n + 1), dfn, loc(n + 1);
	auto dfs = [&](auto &&self, int v, int fa) -> void {
		loc[v] = dfn.size();
		dfn.emplace_back(v);
		for (auto u : e[v]) {
			if (u != fa) {
				dep[u] = dep[v] + 1;
				self(self, u, v);
			}
		}
	};
	dfs(dfs, 1, 1);
	auto isfa = [&](int u, int v) {
		return dep[u] <= dep[v] && dfn[loc[v] - (dep[v] - dep[u])] == u;
	};
	auto check = [&](int x, int v, int y) {
		if (isfa(v, x)) {
			return isfa(y, v) || !isfa(v, y);
		}
		if (isfa(v, y)) {
			return isfa(x, v) || !isfa(v, x);
		}
		return false;
	};
	vector<int> b(m + 1);
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	int cnt = m;
	for (int i = 2; i < m; i++) {
		if (check(b[i - 1], b[i], b[i + 1])) {
			--cnt;
		}
	}
	auto calc = [&](int i) {
		int res = 0;
		if (i >= 3 && check(b[i - 2], b[i - 1], b[i])) {
			++res;
		}
		if (i >= 2 && i < m && check(b[i - 1], b[i], b[i + 1])) {
			++res;
		}
		if (i < m - 1 && check(b[i], b[i + 1], b[i + 2])) {
			++res;
		}
		return res;
	};
	for (int i = 1; i <= q; i++) {
		int p, w;
		cin >> p >> w;
		cnt += calc(p);
		b[p] = w;
		cnt -= calc(p);
		cout << cnt << '\n';
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3

output:

4
4
5

result:

ok 3 number(s): "4 4 5"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3528kb

input:

30 200 200
10 24
10 13
10 26
13 29
27 26
17 24
27 21
17 15
13 5
13 30
27 3
18 21
9 21
2 24
10 4
11 5
2 8
10 23
1 18
21 25
4 20
12 23
22 27
28 27
18 7
13 6
14 30
10 19
16 21
14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16 2...

output:

185
186
187
187
187
187
187
187
187
187
188
188
188
188
188
187
187
187
187
187
187
186
186
186
186
186
186
187
187
186
186
186
186
186
186
186
186
186
186
186
186
186
186
186
187
188
187
187
187
186
187
186
186
186
186
186
186
186
186
186
186
186
185
183
183
183
183
182
182
182
182
182
182
182
181
...

result:

wrong answer 1st numbers differ - expected: '174', found: '185'