QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#626459 | #5403. 树数术 | Flamire | 30 | 898ms | 269172kb | C++17 | 2.7kb | 2024-10-10 09:18:44 | 2024-10-10 09:18:45 |
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];
struct point{int x,id,w;};
vector<point> vv;
int sum[N];
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];}
void push(point p)
{
vv.push_back(p);
sum[vv.size()-1]=(vv.size()>=2?sum[vv.size()-2]:0)+p.w;
}
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().x,a[i]))vv.pop_back();
push({x,i,1});
// printf("i:%d vv:",i);for(point x:vv)printf("{%d,%d,%d} ",x.x,x.id,x.w);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].x,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].id<=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,sum[rb]-(lb>0?sum[lb-1]:0));
}
}
for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
fclose(stdin);fclose(stdout);return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 898ms
memory: 269172kb
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: 20
Accepted
Test #2:
score: 20
Accepted
time: 799ms
memory: 239792kb
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:
211594 160846 176729 128251 32662 70710 74884 9095 68282 91324 154262 24279 31878 173468 75265 139715 91660 87525 194302 16875 81535 172911 29145 20483 151883 5255 9548 58890 38076 94152 14358 74859 48870 23981 41390 60976 13795 125823 427 26641 130620 174231 73241 55291 2364 78864 23391 4866 36002 ...
result:
ok 699992 lines
Subtask #3:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 83ms
memory: 135432kb
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:
5288 11330 2539 2383 5320 21087 1080 8240 8100 834 8917 11977 6312 6132 2427 820 87 18283 792 139 21383 8288 8903 5714 15707 264 533 3283 13883 3828 645 16796 1995 6434 8490 20419 3448 12192 11300 1003 1768 269 4114 743 7340 4485 14902 8747 817 11878 12023 146 7704 3173 268 15606 10316 3008 3540 110...
result:
wrong answer 1st lines differ - expected: '9733', found: '5288'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%