QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602771#8716. 树ITC_TL#WA 2ms11784kbC++203.0kb2024-10-01 12:45:102024-10-01 12:45:12

Judging History

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

  • [2024-10-01 12:45:12]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11784kb
  • [2024-10-01 12:45:10]
  • 提交

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'