QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#627404 | #8716. 树 | Alasco | WA | 2ms | 11328kb | C++14 | 1.6kb | 2024-10-10 15:49:35 | 2024-10-10 15:49:39 |
Judging History
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&&ch(b[x-1],b[x])&&f[x-1]==-1)||(f[x]==1&&f[x-1]==1&&ch(b[x],b[x-1]))||(f[x-1]==1&&f[x]==-1&&!ch(b[x-1],b[x]))){
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);
cout<<sum<<"\n";
}
}
/*
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: 11328kb
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: 10196kb
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:
180 181 181 181 181 181 181 181 182 182 183 183 182 182 182 182 181 181 181 181 180 179 179 179 179 179 179 180 180 180 180 179 178 179 179 179 179 179 179 179 179 179 178 178 178 179 178 178 178 177 178 179 179 179 179 179 179 179 179 179 179 180 179 179 179 179 179 180 180 181 181 181 181 181 180 ...
result:
wrong answer 1st numbers differ - expected: '174', found: '180'