QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859177#9676. AncestorsShumomo0 71ms28604kbC++142.0kb2025-01-17 16:08:532025-01-17 16:08:57

Judging History

你现在查看的是最新测评结果

  • [2025-01-17 16:08:57]
  • 评测
  • 测评结果:0
  • 用时:71ms
  • 内存:28604kb
  • [2025-01-17 16:08:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define tm asdfdfg
int n,m,l,r,u,tm,mp,tt,tmp,tot,d[100009],g[100009],v[100009],lg[100009],dfn[100009],ans[100009],st[100009][22];
set<int> s[100009];
set<int>::iterator it;
vector<int> to[100009];
struct node{
    int l,r,x,id;
    bool operator < (const node aa)const{
        return r<aa.r||(r==aa.r&&id<aa.id);
    }
}q[1000009];
void add(int x){
    it=s[d[x]].lower_bound(dfn[x]);
    tmp=d[x];
//    cout<<x<<" "<<d[x]<<" "<<tmp<<endl;
    if(it!=s[d[x]].end()){
        tm=*it;
        tt=lg[tm-dfn[x]+1];
        mp=min(st[dfn[x]][tt],st[tm-(1<<tt)+1][tt]);
        tmp=min(tmp,d[x]-mp);
//        cout<<x<<" "<<d[x]<<" "<<tmp<<endl;
    }
    if(it!=s[d[x]].begin()){
        it--;
        tm=*it;
        tt=lg[dfn[x]-tm+1];
        mp=min(st[tm][tt],st[dfn[x]-(1<<tt)+1][tt]);
        tmp=min(tmp,d[x]-mp);
//        cout<<x<<" "<<d[x]<<" "<<tmp<<" "<<tm<<" "<<mp<<endl;
    }
    s[d[x]].insert(dfn[x]);
    g[x]=tmp-1;
    for(int i=n+1-g[x];i<=n+1;i+=(i&(-i)))v[i]++;
}
void dfs(int x){
    dfn[x]=++tot;
    for(auto i:to[x]){
        d[i]=d[x]+1;
        dfs(i);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&u);
        to[u].emplace_back(i);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x);
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    dfs(0);
    lg[1]=0;
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++){
        st[dfn[i]][0]=d[i];
    }
    for(int i=1;i<=lg[n];i++){
        for(int j=1;j+(1<<i)<=n;j++){
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
        }
    }
    l=1;
    r=0;
    for(int i=1;i<=m;i++){
        while(r<q[i].r){
            r++;
            add(r);
        }
        tmp=0;
        for(int j=n+1-q[i].x;j;j-=(j&(-j)))tmp+=v[j];
        ans[q[i].id]=tmp;
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 16208kb

input:

7 5
3 1 0 5 3 5 1
1 3 1
5 7 2
1 5 1
4 7 1
4 7 2

output:

2
3
3
4
3

result:

wrong answer 2nd numbers differ - expected: '1', found: '3'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #30:

score: 0
Wrong Answer
time: 71ms
memory: 28604kb

input:

50000 200000
42574 43129 47328 17982 40521 6668 12729 32377 201 11940 8599 11734 18349 41045 26854 22540 9897 33419 7463 1243 47272 27135 49050 49111 22435 42539 39924 20272 5843 9308 45963 3283 31185 13692 38952 20583 15885 24802 4773 953 49907 28689 36942 23550 19449 8970 33340 31665 5407 46023 18...

output:

12072
1327
12370
2475
32809
37028
39185
31040
16761
16995
48336
42266
24077
1825
19174
7069
27509
30915
9298
17017
40463
31502
23214
8070
4021
36889
18667
6870
13467
25014
12480
17705
26332
12391
4251
2389
41200
14194
31780
26412
43116
38273
41276
23016
13035
45955
49523
19874
26233
30012
48616
4673...

result:

wrong answer 1st numbers differ - expected: '12045', found: '12072'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Runtime Error

Test #67:

score: 0
Runtime Error

input:

100000 1000000
6457 23693 90928 23592 90440 75018 16865 3342 83718 16731 95103 31510 38719 27886 29093 41955 6596 46409 51839 10527 91993 61074 14405 34833 53674 42363 11490 43757 46191 6058 59164 96938 57858 40178 97523 84164 21582 72243 11267 47368 97058 6637 95208 60092 53943 16441 28363 64965 52...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%