QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628005#8716. 树AlascoWA 2ms10520kbC++141.9kb2024-10-10 18:05:552024-10-10 18:05:56

Judging History

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

  • [2024-10-10 18:05:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10520kb
  • [2024-10-10 18:05:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;using ll=long long;using ld=long double;using ull=unsigned long long;
using PII=pair<ll,ll>;using pii=pair<int,int>;const ll M=998244353;const ll INF=1e17;
const double eps=1e-10;const double PI=acos(-1.0);const int inf=1e9+7;
int n,m,q,L[200005],cnt,R[200005],b[200005],f[200005],ans[200005],sum;
vector<int>e[200005];
void dfs(int u,int fa){
    L[u]=++cnt;
    for(auto v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    R[u]=cnt;
}
bool ch(int x,int y){
    return (L[y]>=L[x]&&L[y]<=R[x]);
}
void update(int x){
    if(x==1||x>m){
        return;
    }
    
    if(ch(b[x],b[x-1])){
        f[x]=1;
    }else{
        f[x]=-1;
    }
    // if(f[x-1]==1&&f[x]==-1){
    //     cout<<"fu\n";
    //     cout<<x<<" "<<b[x]<<" "<<b[x-1]<<" "<<b[x-2]<<"\n";
    //     cout<<ch(b[x-1],b[x])<<"\n";
    //     cout<<ch(b[x-2],b[x])<<"\n";
    // }
    if((f[x]==-1&&ch(b[x-1],b[x])&&f[x-1]==-1)||(f[x]==1&&f[x-1]==1)||(f[x-1]==1&&f[x]==-1&&(ch(b[x-1],b[x])==0||(ch(b[x-2],b[x])==0&&ch(b[x],b[x-2])==0)))){
        if(f[x]==1&&f[x-1]==1)assert(ch(b[x],b[x-1]));
        if(ans[x]==1)sum--;
        ans[x]=0;
    }else{
        if(ans[x]==0)sum++;
        ans[x]=1;
    }
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    
    ans[1]=1;
    f[1]=0;
    sum=1;
    
    for(int i=2;i<=m;i++){
        update(i);
    }
    
    for(int i=1;i<=q;i++){
        int p,w;cin>>p>>w;
        b[p]=w;
        update(p);
        update(p+1);
        update(p+2);
        assert(sum>=2&&sum<=m);
        // for(int j=1;j<=m;j++){
        //     cout<<ans[j]<<" ";
        // }cout<<"\n";
        cout<<sum<<"\n";
    }
}

详细

Test #1:

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

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: 2ms
memory: 9908kb

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:

156
157
157
157
156
156
156
157
157
157
158
158
158
158
157
157
156
156
156
156
155
155
155
155
155
154
154
154
154
154
154
153
153
154
154
154
155
155
155
155
155
155
154
154
154
154
154
155
156
155
156
156
156
155
156
156
156
157
157
157
158
159
159
159
159
159
159
160
160
161
161
160
161
159
158
...

result:

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