QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603277#8716. 树frsWA 549ms17132kbC++142.9kb2024-10-01 15:39:052024-10-01 15:39:06

Judging History

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

  • [2024-10-01 15:39:06]
  • 评测
  • 测评结果:WA
  • 用时:549ms
  • 内存:17132kb
  • [2024-10-01 15:39:05]
  • 提交

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;
}

int dis(int x, int y){
    int z = lca(x, y);
    return dep[y]+dep[x]-2*dep[z];
}

bool check(int x, int y, int on){
    return dis(x, on)+ dis(y, on) == dis(x, y);
}

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 j = 1; j <= 20; ++j) {
        for (int i = 1; i <= n; ++i) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (s.size() <= 1) s.insert(i);
        else{
            auto j = s.rbegin();
            j++;
            if (check(b[*j], b[i], b[*s.rbegin()])) s.erase(*s.rbegin());
            s.insert(i);
        }
    }
    while (q--){
        cin >> x >> y;
        if (m == 1 || m == 2){
            cout << m << "\n";
            continue;
        }
        b[x]=y;
        auto i=s.lower_bound(x);
        i--;
        if(i!=s.begin()) i--;
        if(i!=s.begin()) i--;
        if(i!=s.begin()) i--;
        s.insert(x);
        if(x!=1) s.insert(x-1);
        if(x!=m) s.insert(x+1);
        for(int PO=0;PO < 7;PO++){
            if(i==s.end()) break;
            auto j=i;
            j++;
            if(j==s.end()) break;
            auto k=j;
            k++;
            if(k==s.end()) break;
            if(check(b[*i], b[*k], b[*j])) s.erase(*j);
            else i++;
        }
        printf("%d\n",(int)s.size());
    }
}

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

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: 0
Accepted
time: 2ms
memory: 12508kb

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:

174
175
175
175
175
175
175
175
175
175
176
176
176
176
176
176
175
175
175
175
174
173
173
173
173
173
173
174
174
174
174
173
173
174
174
174
174
174
174
174
174
174
173
173
173
174
173
173
174
173
174
174
174
174
174
174
174
174
174
174
174
175
174
174
174
174
174
175
175
177
177
177
177
177
176
...

result:

ok 200 numbers

Test #3:

score: -100
Wrong Answer
time: 549ms
memory: 17132kb

input:

1000 200000 200000
142 266
266 877
877 673
673 473
923 473
923 55
55 288
679 288
85 679
85 460
296 460
793 296
262 793
40 262
40 680
647 680
999 647
56 999
550 56
550 774
774 939
939 423
423 168
168 554
554 93
329 93
329 474
221 474
890 221
890 304
752 304
345 752
345 269
290 269
290 781
781 264
859...

output:

133598
133598
133598
133598
133598
133598
133596
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133596
133596
133596
133596
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133596
133596
133596
133596
133596...

result:

wrong answer 140343rd numbers differ - expected: '133344', found: '133345'