QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602771 | #8716. 树 | ITC_TL# | WA | 2ms | 11784kb | C++20 | 3.0kb | 2024-10-01 12:45:10 | 2024-10-01 12:45:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fore(i, l, r) for (int i = (int)l; i <= (int)r; i++)
#define ford(i, r, l) for (int i = (int)r; i >= (int)l; i--)
const int MAXN = 412345LL;
ll T, n, m, q, dep[MAXN];
ll hand[MAXN], to[MAXN], nxt[MAXN], tot;
ll fa[MAXN][32], b[MAXN];
ll er[MAXN];
void pre()
{
er[0] = 1;
fore(i, 1, 31) er[i] = er[i - 1] * 2;
return;
}
void add(ll x, ll y)
{
tot++;
to[tot] = y;
nxt[tot] = hand[x];
hand[x] = tot;
}
ll cen(ll x, ll y)
{
if (y < 0)
return -1;
ford(i, 31, 0)
{
if (y >= er[i])
{
y -= er[i];
x = fa[x][i];
}
}
return x;
}
ll lca(ll x, ll y)
{
if (dep[x] < dep[y])
swap(x, y);
if (dep[x] > dep[y])
{
x = cen(x, dep[y] - dep[x]);
}
if (x == y)
return x;
ford(i, 31, 0)
{
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
}
fore(i, 0, 31)
{
if (fa[x][i] == fa[y][i])
return fa[x][i];
}
}
void sou(ll t)
{
fore(i, 1, 31)
fa[t][i] = fa[fa[t][i - 1]][i - 1];
for (register int i = hand[t]; i; i = nxt[i])
{
if (!fa[to[i]][0] && to[i] != 1)
{
fa[to[i]][0] = t;
dep[to[i]] = dep[t] + 1;
sou(to[i]);
}
}
return;
}
bool nei(ll tar, ll x, ll y)
{
ll cen1 = cen(x, dep[x] - dep[tar]);
ll cen2 = cen(y, dep[y] - dep[tar]);
ll lc = lca(x, y);
if ((cen1 == tar || cen2 == tar) && dep[tar] >= dep[lc])
return 1;
return 0;
}
bool vis[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
pre();
cin >> n >> m >> q;
ll l, r;
fore(i, 1, n - 1)
{
cin >> l >> r;
add(l, r);
add(r, l);
}
dep[1] = 1;
sou(1);
fore(i, 1, m)
{
cin >> b[i];
}
ll cnt = 1;
l = 1, r = 2;
vis[l] = 1;
fore(i, 3, m)
{
if (nei(b[r], b[l], b[i]))
{
r = i;
continue;
}
l = r;
vis[l] = 1;
r = i;
cnt++;
}
// cout << cnt << endl;
if (l != n)
vis[n] = 1, cnt++;
while (q--)
{
cin >> l >> r;
if (vis[l] == 0)
vis[l] = 1, cnt++;
if (l - 1 >= 1 && vis[l - 1] == 0)
vis[l - 1] = 1, cnt++;
if (l + 1 <= n && vis[l + 1] == 0)
vis[l + 1] = 1, cnt++;
if (l - 2 >= 1 && nei(b[l - 1], r, b[l - 2]) && vis[l - 1] == 1)
vis[l - 1] = 0, cnt--;
if (l + 2 <= n && nei(b[l + 1], r, b[l + 2]) && vis[l + 1] == 1)
vis[l + 1] = 0, cnt--;
b[l] = r;
if (vis[l] == 1 && (nei(b[l], b[l - 1], b[l + 1])))
{
vis[l] = 0, cnt--;
}
cout << cnt << endl;
}
return 0;
}
/*
5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9784kb
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: 11784kb
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:
151 152 152 152 151 151 151 152 152 152 152 152 152 152 151 150 149 149 150 150 149 148 149 149 149 149 149 149 149 150 150 149 148 148 148 148 149 149 149 149 149 149 148 148 149 150 149 151 152 152 153 153 152 151 151 151 150 151 151 151 152 153 152 152 152 152 153 152 152 152 152 151 152 154 153 ...
result:
wrong answer 1st numbers differ - expected: '174', found: '151'