QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602675#8716. 树frs#WA 0ms12768kbC++143.0kb2024-10-01 11:54:082024-10-01 11:54:09

Judging History

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

  • [2024-10-01 11:54:09]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:12768kb
  • [2024-10-01 11:54:08]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include <valarray>
#include <cmath>
#include <numeric>
#include <random>
#include <set>

using namespace std;

#define ll long long
//#define int ll

const int maxN = 2e5+10, mod = 998244353, inf = 1e9+10;
int n, m, q, b[maxN], fa[maxN][30], dep[maxN];

ll power(ll x, ll y){
    ll an = 1;
    while(y){
        if (y&1) an = an*x % mod;
        y >>= 1;
        x = x*x %mod;
    }
    return an;
}

ll inv(ll x){
    return power(x, mod-2);
}

vector<int> v[maxN];
set<int> s;

void dfs(int x, int last, int d){
    dep[x] = d;
    fa[x][0] = last;
    for (auto i:v[x]){
        if (i == last) continue;
        dfs(i, x, d+1);
    }
}

int lca(int x, int y){
    if (dep[x] > dep[y]) swap(x, y);
    int z = dep[y]-dep[x], c = 0;
    while (z){
        if (z & 1) y = fa[y][c];
        z >>= 1;
        c++;
    }
    if (x == y) return x;
    for (int i = 20; i >= 0; --i) {
        if (fa[x][i] == fa[y][i]) continue;
        x = fa[x][i];
        y = fa[y][i];
    }
    return fa[x][0];
}

bool is_fa(int son, int f){
    if (son == f) return false;
    return lca(son, f) == f;
}

bool check(int x, int y, int on){
    if (dep[x] > dep[y]) swap(x, y);
    if (dep[on] < dep[x]) return lca(x, on) == on && lca(y, on) == on;
    if (dep[on] > dep[y]) return false;
    return lca(x, on) == x && lca(y, on) == on;
}

void solve(){
    cin >> n >> m >> q;
    int x, y;
    for (int i = 1; i < n; ++i) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1; i <= m; ++i) cin >> b[i];
    dfs(1, 0, 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 20; ++j) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (!s.empty() && b[i] == *s.rbegin()) continue;
        if (s.size() <= 1) s.insert(i);
        else{
            auto j = s.rbegin();
            j++;
            if (check(b[*j], b[i], b[*s.rbegin()])) continue;
            else s.erase(*s.rbegin()), s.insert(i);
        }
    }
    while (q--){
        cin >> x >> y;
        if (m == 1){
            cout << 1 << "\n";
            continue;
        }
        b[x] = y;
        if (x == 1){
            auto i = s.lower_bound(x);
            if (!check(b[*i], b[x], b[x+1])) s.insert(x+1);
            cout << s.size()+1 << "\n";
        }else if (x == n){
            auto i = s.rbegin();
            i++;
            if (!check(b[*i], b[x], b[x-1])) s.insert(x-1);
            cout << s.size()+1 << "\n";
        }else{
            if (!check(b[x-1], b[x+1], b[x])){
                if (check(b[x-1], b[x], b[x+1])) s.insert(x+1), s.insert(x);
                else s.insert(x), s.insert(x-1);
            }
            cout << s.size()+1 << "\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie();
    int t = 1;
    while (t--) solve();
    return 0;
}

詳細信息

Test #1:

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

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: 10796kb

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:

5
7
9
10
10
12
14
16
18
20
22
24
26
28
30
32
34
36
37
38
40
42
44
46
48
48
50
51
53
55
57
57
57
57
59
61
63
65
67
69
69
71
72
73
75
76
78
80
81
81
81
82
84
84
86
87
87
87
89
91
91
93
93
93
93
94
94
95
96
98
99
99
101
101
101
103
103
103
104
106
108
108
110
112
113
115
115
115
115
115
117
117
119
121...

result:

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