QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #603495 | #8716. 树 | Zaria | WA | 0ms | 16168kb | C++17 | 4.4kb | 2024-10-01 16:55:28 | 2024-10-01 16:55:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define PLL pair<ll,ll>
#define ll long long
const ll N=2e5+10,mod=1e9+7;
ll n,m,q;
ll h[N],ne[N*2],e[N*2],idx;
ll bb[N],st[N];
ll fa[N][20],d[N],ud[N];
ll root;
bool sst[N];
void add(ll m,ll n){
e[idx]=n,ne[idx]=h[m],h[m]=idx++;
}
void dfs(ll x){
sst[x]=1;
for(int i=1;(1<<i)<=d[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=h[x];i!=-1;i=ne[i]){
ll j=e[i];
if(sst[j]==0){
d[j]=d[x]+1;
fa[j][0]=x;
dfs(j);
}
}
}
ll lca(ll a,ll b){
if(d[a]<d[b]) swap(a,b);
for(int i=18;i>=0;i--){
if(d[fa[a][i]]<d[b]) continue;
a=fa[a][i];
}
if(a==b) return a;
for(int i=18;i>=0;i--){
if(fa[a][i]==fa[b][i]) continue;
a=fa[a][i];
b=fa[b][i];
}
return fa[a][0];
}
int main(){
cin>>n>>m>>q;
memset(h,-1,sizeof h);
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
d[1]=1;
dfs(1);
for(int i=1;i<=m;i++){
cin>>bb[i];
}
ud[1]=0;
st[1]=1;
ll t=lca(bb[1],bb[2]);
if(t==bb[1]){
ud[2]=1;//1 下 2 上
}
if(t==bb[2]){
ud[2]=2;
}
if(t!=bb[1]&&t!=bb[2]){
ud[2]=1;
}
for(int i=2;i<n;i++){
t=lca(bb[i],bb[i+1]);
if(t!=bb[i]&&t!=bb[i+1]){
ud[i+1]=1;
st[i]=1;
}
if(t==bb[i]){
if(ud[i]==2){
st[i]=1;
ud[i+1]=1;
}
else{
st[i]=0;
ud[i+1]=1;
}
}
if(t==bb[i+1]){
if(ud[i]==2){
st[i]=0;
ud[i+1]=2;
}
else{
st[i]=1;
ud[i+1]=2;
}
}
}
ll res=0;
st[n]=1;
for(int i=1;i<=n;i++){
if(st[i]==1) res++;
}
for(int i=1;i<=q;i++){
ll p,w;
cin>>p>>w;
bb[p]=w;
if(p==1){
ll pre=ud[2];
t=lca(bb[1],bb[2]);
if(t==bb[1]){
ud[2]=1;//1 下 2 上
}
if(t==bb[2]){
ud[2]=2;
}
if(t!=bb[1]&&t!=bb[2]){
ud[2]=1;
}
if(pre!=ud[2]){
pre=st[2];
if(ud[2]==ud[3]){
st[2]==0;
}
else{
st[2]==1;
}
res+=st[2]-pre;
}
}
if(p==n){
ll pre=ud[n];
t=lca(bb[n-1],bb[n]);
if(t==bb[n]){
ud[n]=2;//1 下 2 上
if(pre!=ud[n]){
pre=st[n-1];
st[n-1]=1;
res+=st[n-1]-pre;
}
}
if(t==bb[n-1]){
ud[n]=1;
if(pre!=ud[n]){
pre=st[n-1];
st[n-1]=1;
res+=st[n-1]-pre;
}
}
if(t!=bb[n-1]&&t!=bb[n]){
ud[n]=1;
if(pre!=ud[n]){
pre=st[n-1];
st[n-1]=1;
res+=st[n-1]-pre;
}
}
}
if(p!=1&&p!=n){
ll pre=st[p-1]+st[p]+st[p+1];
for(int j=p-1;j<=p+1;j++){
t=lca(bb[j],bb[j+1]);
if(t!=bb[j]&&t!=bb[j+1]){
ud[j+1]=1;
st[j]=1;
}
if(t==bb[j]){
if(ud[j]==2){
st[j]=1;
ud[j+1]=1;
}
else{
st[j]=0;
ud[j+1]=1;
}
}
if(t==bb[j+1]){
if(ud[j]==2){
st[j]=0;
ud[j+1]=2;
}
else{
st[j]=1;
ud[j+1]=2;
}
}
}
res+=st[p-1]+st[p]+st[p+1]-pre;
}
cout<<res<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15368kb
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: 16168kb
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:
28 31 33 33 36 39 39 41 43 46 48 51 54 57 60 63 64 67 69 69 72 73 75 77 79 81 84 84 86 88 88 88 89 89 92 95 96 98 101 101 101 104 105 106 109 110 112 114 115 115 116 117 119 119 119 120 120 120 123 125 125 128 130 130 130 130 129 131 131 134 135 135 135 135 134 137 138 138 138 141 142 142 145 148 14...
result:
wrong answer 1st numbers differ - expected: '174', found: '28'