QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80709 | #5403. 树数术 | zhouhuanyi | 0 | 2191ms | 153148kb | C++14 | 2.7kb | 2023-02-24 21:49:19 | 2023-02-24 21:49:20 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 700000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,m,q,depth[N+1],a[N+1],fa[N+1],lg[N+1],hs[N+1],dfn[N+1],top[N+1],leng,sz[N+1],tong[N+1],length;
bool used[N+1];
long long ans;
vector<int>E[N+1];
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x);
return;
}
void dfs(int x)
{
used[x]=sz[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
{
fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,dfs(E[x][i]),sz[x]+=sz[E[x][i]];
if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
}
return;
}
void dfs2(int x)
{
dfn[x]=++leng;
if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
for (int i=0;i<E[x].size();++i)
if (fa[E[x][i]]==x&&E[x][i]!=hs[x])
top[E[x][i]]=E[x][i],dfs2(E[x][i]);
return;
}
int lca(int x,int y)
{
while (top[x]!=top[y])
{
if (depth[top[x]]<depth[top[y]]) swap(x,y);
x=fa[top[x]];
}
if (depth[x]<depth[y]) swap(x,y);
return y;
}
bool LENG(int x,int y)
{
return dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+sz[x]-1;
}
struct seg
{
struct node
{
int l,r,data,res;
};
node tree[(N<<2)+1];
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r,tree[k].data=a[l],tree[k].res=1;
for (int i=l+1;i<=r;++i)
{
tree[k].data=lca(tree[k].data,a[i]);
if (tree[k].data==a[i]) tree[k].res++;
}
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r);
return;
}
int query(int k,int d)
{
if (tree[k].l==tree[k].r) return LENG(d,tree[k].data);
if (LENG(tree[k<<1].data,d)) return query(k<<1,d)+tree[k].res-tree[k<<1].res;
else if (LENG(d,tree[k<<1].data)) return query(k<<1|1,d);
else return query(k<<1|1,lca(d,tree[k<<1].data));
}
void solve(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r)
{
tong[++length]=k;
return;
}
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) solve(k<<1,l,r);
else if (l>=mid+1) solve(k<<1|1,l,r);
else solve(k<<1,l,mid),solve(k<<1|1,mid+1,r);
return;
}
};
seg T;
int main()
{
int k,x,y,l,r,d;
n=read(),m=read(),q=read();
for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
depth[1]=top[1]=1,dfs(1),dfs2(1);
for (int i=1;i<=m;++i) a[i]=read();
T.build(1,1,m);
while (q--)
{
k=read(),length=0;
while (k--) l=read(),r=read(),T.solve(1,l,r);
d=T.tree[tong[1]].data,ans=T.tree[tong[1]].res;
for (int i=2;i<=length;++i) ans+=T.query(tong[i],d),d=lca(d,T.tree[tong[i]].data);
printf("%lld\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1798ms
memory: 153148kb
input:
699990 699995 233333 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
122060 139525 87469 42807 311786 194311 177806 454200 417122 299507 366096 227761 186415 163955 292515 216120 401703 16625 192712 27344 52126 54929 142186 275124 339854 117007 51157 229183 187646 350022 398520 83936 100513 338065 356683 60212 366252 142638 16914 222321 471114 184168 170757 238373 14...
result:
wrong answer 1st lines differ - expected: '121987', found: '122060'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 2191ms
memory: 125172kb
input:
699992 699994 699992 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 40 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
211596 160848 176726 128252 32659 70708 74879 9096 68278 91328 154262 24278 31878 173467 75271 139717 91661 87526 194302 16874 81534 172916 29151 20486 151882 5256 9550 58885 38079 94152 14354 74848 48869 23980 41391 60974 13802 125820 425 26642 130621 174232 73242 55289 2360 78870 23392 4867 36002 ...
result:
wrong answer 1st lines differ - expected: '211594', found: '211596'
Subtask #3:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 177ms
memory: 47928kb
input:
99998 99993 33333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 24 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 49 ...
output:
9731 11330 8401 5134 22203 23232 12681 27289 23732 20941 18149 16379 8991 14029 11665 14680 20270 18954 21668 7929 21383 23574 14818 5715 15705 10009 7908 13252 13881 10442 16137 16791 11004 11915 15767 20420 11159 12185 14328 18250 19087 5240 4112 16504 7415 5002 16844 8742 19374 22600 12022 9162 9...
result:
wrong answer 1st lines differ - expected: '9733', found: '9731'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%