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

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

[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
*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 9784kb

input:

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:

result:

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