QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#623365 | #8716. 树 | bruteforce_ | WA | 1ms | 3632kb | C++20 | 2.1kb | 2024-10-09 11:32:43 | 2024-10-09 11:32:43 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,mod=998244353,S=21;
int n,m,Q;
vector<vector<int>> e,fa;
vector<int> dep;
void dfs(int u)
{
dep[u]=dep[fa[u][0]]+1;
for(auto v:e[u])
{
if(v==fa[u][0]) continue;
fa[v][0]=u;
dfs(v);
}
for(int i=1; i<S; i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=S-1; i>=0; i--)
{
if(dep[fa[x][0]]>=dep[y])
{
x=fa[x][0];
}
}
if(x==y) return x;
for(int i=S-1; i>=0; i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
void O_o()
{
cin>>n>>m>>Q;
e.assign(n+1,vector<int>());
fa.assign(n+1,vector<int>(S,0));
dep.assign(n+1,0);
for(int i=1; i<n; i++)
{
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1);
vector<int> b(2*m),ls(2*m);
vector<bool> del(2*m,0);
cin>>b[1];
for(int i=2; i<=m; i++)
{
cin>>b[i*2-1];
b[i*2-2]=lca(b[i*2-3],b[i*2-1]);
}
ls[2]=1;
int tot=0;
for(int i=2; i<2*m-1; i++)
{
int l1=lca(b[ls[i]],b[i]),l2=lca(b[i],b[i+1]),l3=lca(b[ls[i]],b[i+1]);
if((l1==b[i]||l2==b[i]||l3==b[i])&&b[ls[i]]!=b[i+1])
{
// if(i&1)
// cout<<i/2+1<<"\n";
del[i]=1;
tot++;
ls[i+1]=ls[i];
}
else
{
del[i]=0;
ls[i+1]=i;
}
}
// cout<<2*n-1-tot<<"\n";
while(Q--)
{
int id,x;
cin>>id>>x;
id=id*2-1;
b[id]=x;
if(id>1)
{
b[id-1]=lca(b[id-2],b[id]);
}
if(id<m*2-1)
{
b[id+1]=lca(b[id],b[id+2]);
}
for(int i=max(2ll,id-4); i<=min(2*m-1,id+4); i++)
{
tot-=del[i];
int l1=lca(b[ls[i]],b[i]),l2=lca(b[i],b[i+1]),l3=lca(b[ls[i]],b[i+1]);
if((l1==b[i]||l2==b[i]||l3==b[i])&&b[ls[i]]!=b[i+1])
{
del[i]=1;
tot++;
ls[i+1]=ls[i];
}
else
{
del[i]=0;
ls[i+1]=i;
}
}
cout<<2*n-1-tot<<"\n";
}
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(12);
int T=1;
// cin>>T;
while(T--)
{
O_o();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: 1ms
memory: 3632kb
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:
-192 -191 -191 -191 -192 -192 -192 -191 -191 -191 -190 -190 -190 -190 -191 -192 -193 -193 -193 -193 -194 -195 -195 -195 -195 -196 -196 -196 -196 -195 -195 -196 -197 -196 -196 -196 -195 -195 -195 -195 -195 -195 -196 -196 -195 -194 -195 -194 -193 -194 -193 -193 -195 -196 -195 -195 -195 -194 -194 -194 ...
result:
wrong answer 1st numbers differ - expected: '174', found: '-192'