QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417828 | #8716. 树 | wsyear | WA | 0ms | 11116kb | C++17 | 1.8kb | 2024-05-22 22:58:19 | 2024-05-22 22:58:20 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
const int maxn = 200010;
int n, m, q, fa[maxn][20], dep[maxn], a[maxn];
vector<int> e[maxn];
void dfs(int u, int f) {
fa[u][0] = f, dep[u] = dep[f] + 1;
for (int v : e[u]) if (v != f) dfs(v, u);
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int dc = dep[u] - dep[v];
per (i, 19, 0) if (dc >> i & 1) u = fa[u][i];
if (u == v) return u;
per (i, 19, 0) if (fa[u][i] == fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
int dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int check(int x, int y, int z) {
return dis(x, z) == dis(x, y) + dis(y, z);
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> n >> m >> q;
rep (i, 1, n - 1) {
int u, v;
cin >> u >> v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
rep (i, 1, m) cin >> a[i];
dfs(1, 0);
rep (j, 1, 19) rep (i, 1, n) fa[i][j] = fa[fa[i][j - 1]][j - 1];
int ans = 0;
rep (i, 2, m - 1) if (check(a[i - 1], a[i], a[i + 1])) ans++;
while (q--) {
int x, y;
cin >> x >> y;
rep (i, max(2, x - 1), min(m - 1, x + 1)) if (check(a[i - 1], a[i], a[i + 1])) ans--;
a[x] = y;
rep (i, max(2, x - 1), min(m - 1, x + 1)) if (check(a[i - 1], a[i], a[i + 1])) ans++;
cout << m - ans << '\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11116kb
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: 10984kb
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:
180 181 181 181 181 181 181 181 182 182 183 183 182 182 182 182 181 181 181 181 180 179 179 179 179 179 179 180 180 180 180 179 178 179 179 179 179 179 179 179 179 179 178 178 178 179 178 178 178 177 178 179 179 179 179 179 179 179 179 179 179 180 179 179 179 179 179 180 180 181 181 181 181 181 180 ...
result:
wrong answer 1st numbers differ - expected: '174', found: '180'