QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80101 | #5403. 树数术 | tricyzhkx | 20 | 982ms | 327564kb | C++14 | 2.5kb | 2023-02-22 08:37:48 | 2023-02-22 08:37:50 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int SIZE=(1<<21)+1;
typedef long long ll;
char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=obuf;
char* flush(){fwrite(obuf,1,oT-oS,stdout);return oT=obuf;}
struct Flusher{~Flusher(){flush();}}flusher;
# define gc() (iS==iT && (iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT)?EOF:*iS++)
# define pc(c) ((oT==oS+SIZE && flush()),*oT++=(c))
int read()
{
int x=0;
char ch=gc();
for(;ch<'0' || ch>'9';ch=gc());
for(;ch>='0' && ch<='9';ch=gc()) x=x*10+ch-'0';
return x;
}
void write(ll x)
{
if(x>=10) write(x/10);
pc(x%10+'0');
}
vector<int> G[700010];
int a[700010],stk[700010],nxt[700010][20],top[20][700010],dep[700010],dfn[700010],sz[700010],opn[700010],minn[21][1400010],tot,tot2;
int Low(int u,int v){return dep[u]<dep[v]?u:v;}
int lca(int u,int v)
{
u=opn[u];v=opn[v];
if(u>v) swap(u,v);
int k=__lg(v-u+1);
return Low(minn[k][u],minn[k][v-(1<<k)+1]);
}
bool in(int u,int v){return dfn[u]<=dfn[v] && dfn[v]<dfn[u]+sz[u];}
int Top(int l,int r)
{
int k=__lg(r-l+1);
return lca(top[k][l],top[k][r-(1<<k)+1]);
}
void dfs(int u,int fa)
{
sz[u]=1;dfn[u]=++tot;
opn[u]=++tot2;minn[0][tot2]=u;
for(int v:G[u])
{
if(v==fa) continue;
dep[v]=dep[u]+1;
dfs(v,u);sz[u]+=sz[v];
minn[0][++tot2]=u;
}
}
int calc(int &u,int l,int r)
{
int ans=0,p=l;
if(u && !in(a[p],u))
{
for(int i=19;i>=0;i--)
if(!in(a[nxt[p][i]],u))
p=nxt[p][i];
p=nxt[p][0];
}
if(p>r) return 0;
for(int i=19;i>=0;i--)
if(nxt[p][i]<=r) ans+=1<<i,p=nxt[p][i];
u=u?lca(u,Top(l,r)):Top(l,r);
return ans+1;
}
int main()
{
int n,m,q,u,v;
n=read();m=read();q=read();
for(int i=1;i<n;i++)
{
u=read();v=read();
G[u].push_back(v);G[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=tot2;j++)
minn[i][j]=Low(minn[i-1][j],minn[i-1][j+(1<<(i-1))]);
for(int i=1;i<=m;i++) a[i]=read();
int tp=0;
stk[0]=m+1;nxt[m+1][0]=m+1;
for(int i=m;i>=1;i--)
{
int u=a[i];
while(tp && !in(a[stk[tp]],u)) u=lca(u,a[stk[tp]]),tp--;
nxt[i][0]=stk[tp];stk[++tp]=i;
}
for(int i=m+1;i>=1;i--)
for(int j=1;j<=19;j++)
nxt[i][j]=nxt[nxt[i][j-1]][j-1];
for(int i=1;i<=m;i++) top[0][i]=a[i];
for(int i=1;i<=19;i++)
for(int j=1;j+(1<<i)-1<=m;j++)
top[i][j]=lca(top[i-1][j],top[i-1][j+(1<<(i-1))]);
while(q--)
{
int k=read(),l,r,u=0;
ll ans=0;
while(k--) l=read(),r=read(),ans+=calc(u,l,r);
write(ans);pc('\n');
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 660ms
memory: 327564kb
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 133434 87432 18265 285143 194269 177810 454211 417130 299450 240901 227736 186417 163975 292497 216139 367014 16634 192685 27351 52127 51646 142169 182616 339876 117003 51132 229206 187647 268093 398455 83905 95731 157096 178338 60211 366172 65279 16903 222331 471095 184145 144524 155389 1407...
result:
wrong answer 2nd lines differ - expected: '139520', found: '133434'
Subtask #2:
score: 20
Accepted
Test #2:
score: 20
Accepted
time: 982ms
memory: 298332kb
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: 72ms
memory: 57900kb
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:
9733 11330 2539 5136 16099 23231 11401 8240 16249 3378 8917 11977 8991 10057 6099 2525 9760 18955 12750 3119 21383 14977 12263 5714 15707 452 533 13254 13883 10446 7035 16796 11009 6434 15761 20419 11157 12192 14327 3733 8967 5239 4114 6407 7340 4697 15415 8747 7057 11878 12023 1218 8380 6371 1802 1...
result:
wrong answer 3rd lines differ - expected: '8403', found: '2539'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%