QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#626445 | #5403. 树数术 | Flamire | 10 | 963ms | 261908kb | C++17 | 2.6kb | 2024-10-10 09:05:19 | 2024-10-10 09:05:20 |
Judging History
answer
#include <bits/stdc++.h>
#define N 700011
#define pii pair<int,int>
#define s1 first
#define s2 second
#define ll long long
using namespace std;
int n,m,q,a[N];
vector<int> G[N];int dfn[N],siz[N],dep[N],h[N],st[21][N],rk[N],clk,lg[N];
void dfs(int u,int F)
{
dfn[u]=++clk;dep[u]=dep[F]+1;rk[clk]=u;h[clk]=u;siz[u]=1;
for(int v:G[u])if(v^F)
{
dfs(v,u);
h[clk]=u;siz[u]+=siz[v];
}
}
int lca(int x,int y)
{
if(x==y)return x;
if(rk[x]>rk[y])swap(x,y);
int logl=lg[rk[y]-rk[x]];
int u1=st[logl][rk[x]],u2=st[logl][rk[y]-(1<<logl)];
return dep[u1]<dep[u2]?u1:u2;
}
int rg[21][N];
int qlca(int l,int r)
{
if(l==r)return l;
int logl=lg[r-l];
int u1=rg[logl][l],u2=rg[logl][r-(1<<logl)];
return lca(u1,u2);
}
struct kueri{int x,y,k,id;};
vector<kueri> vk[N];
vector<pii> vv;
int ql[N],qr[N];
ll ans[N];
bool insub(int u,int v){return dfn[u]<=dfn[v]&&dfn[v]<dfn[u]+siz[u];}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}
dfs(1,0);
for(int i=1;i<n;++i)st[0][i]=h[i];
for(int i=1;i<=20;++i)
{
for(int j=1;j+(1<<i)-1<n;++j)
{
int u1=st[i-1][j],u2=st[i-1][j+(1<<i-1)];
st[i][j]=dep[u1]<dep[u2]?u1:u2;
}
}
lg[0]=-1;for(int i=1;i<N;++i)lg[i]=lg[i>>1]+1;
for(int i=1;i<=m;++i)scanf("%d",a+i);
for(int i=1;i<m;++i)rg[0][i]=lca(a[i],a[i+1]);
for(int i=1;i<=20;++i)
{
for(int j=1;j+(1<<i)-1<m;++j)
{
int u1=rg[i-1][j],u2=rg[i-1][j+(1<<i-1)];
rg[i][j]=lca(u1,u2);
}
}
for(int i=1;i<=q;++i)
{
int k;scanf("%d",&k);
for(int j=1;j<=k;++j)scanf("%d%d",ql+j,qr+j);
int x=-1;
for(int j=1;j<=k;++j)
{
vk[ql[j]].push_back({ql[j],qr[j],x,i});
// printf("([%d,%d],x:%d) ",ql[j],qr[j],x);
if(~x)x=lca(x,qlca(ql[j],qr[j]));
else x=qlca(ql[j],qr[j]);
}
// putchar(10);
}
for(int i=m;i;--i)
{
int x=a[i];
while(!vv.empty()&&!insub(vv.back().s1,a[i]))x=lca(vv.back().s1,a[i]),vv.pop_back();
vv.push_back({x,i});
// printf("i:%d vv:",i);for(pii x:vv)printf("{%d,%d} ",x.s1,x.s2);putchar(10);
for(kueri k:vk[i])
{
int L=0,R=(int)vv.size()-1,rb=-1;
if(~k.k)
{
while(L<=R)
{
int M=L+R>>1;
if(insub(vv[M].s1,k.k))rb=M,L=M+1;else R=M-1;
}
}
else rb=(int)vv.size()-1;
L=0,R=(int)vv.size()-1;int lb=vv.size();
while(L<=R)
{
int M=L+R>>1;
if(vv[M].s2<=k.y)lb=M,R=M-1;else L=M+1;
}
// printf("query([%d,%d],x:%d) lb:%d rb:%d\n",k.x,k.y,k.k,lb,rb);
ans[k.id]+=max(0,rb-lb+1);
}
}
for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
fclose(stdin);fclose(stdout);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 963ms
memory: 261908kb
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:
121987 139520 87432 42773 311773 194269 177810 454211 417130 299450 366103 227736 186417 163975 292497 216139 401719 16634 192685 27351 52127 54938 142169 275076 339876 117003 51132 229206 187647 350043 398455 83905 100490 338070 356664 60211 366172 142627 16903 222331 471095 184145 170758 238393 14...
result:
ok 233333 lines
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 686ms
memory: 234676kb
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:
40532 1 1 1 1 19424 1 1 7685 13612 34566 1 1 4584 1 1 1 1 20904 1 1 12638 1 22842 1 1 1 1 1 1 17435 1 1 1 1 1 1 1 1 1 1 8104 1 17860 1 1 1 5332 1 1 1 1 1 1 23026 1 1 1 1 1 16008 1 1 1 1 1 1 1 1 1 1 5114 23529 1 8158 1 1 1 1 1 1 1 1 1 1 1 4685 1 13376 1 1 3637 29719 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16213 ...
result:
wrong answer 1st lines differ - expected: '211594', found: '40532'
Subtask #3:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 63ms
memory: 141440kb
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:
1 2 1 3245 2274 4571 75 2314 5788 1372 5849 1 1 3849 410 1260 125 554 1322 175 1 1456 1970 1741 1 382 715 1592 1 1 707 1 3009 1 1 1 1 2 5510 1682 2511 350 1 1251 1 1 2118 1 1110 3397 101 247 5179 3118 372 1 2304 1 1 1826 1496 912 473 1 889 1 558 1212 1 2576 1 13 1 196 5766 1757 1 2350 1 1 3623 1 501...
result:
wrong answer 1st lines differ - expected: '9733', found: '1'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%