QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345134#5020. 举办乘凉州喵,举办乘凉州谢谢喵ANIG0 395ms46172kbC++143.5kb2024-03-06 10:11:032024-03-06 10:11:04

Judging History

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

  • [2024-03-06 10:11:04]
  • 评测
  • 测评结果:0
  • 用时:395ms
  • 内存:46172kb
  • [2024-03-06 10:11:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,mk[N],siz[N],zs[N],d[N],fa[N],dep[N],zd[N],cd[N],rs[N],bk[N],rt,zx[N],sm[N],mx,MX,jl[N];
vector<int>p[N];
vector<pair<int,int> >g[N];
void dfs1(int x){
    mk[x]=1;siz[x]=1;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        fa[c]=x;
        dep[c]=dep[x]+1;
        dfs1(c);
        if(siz[c]>siz[zs[x]])zs[x]=c;
        siz[x]+=siz[c];
        if(zd[c]+1>zd[x])cd[x]=zd[x],zd[x]=zd[c]+1;
        else if(zd[c]+1>cd[x])cd[x]=zd[c]+1;
    }
    mk[x]=0;
}
void dfs2(int x,int y){
    d[x]=y;mk[x]=1;
    if(zs[x])dfs2(zs[x],y);
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        dfs2(c,c);
    }
}
int lca(int a,int b){
    while(d[a]!=d[b]){
        if(dep[d[a]]>dep[d[b]])swap(a,b);
        b=fa[d[b]];
    }
    if(dep[a]>dep[b])swap(a,b);
    return a;
}
void dfs3(int x){
    MX=max(MX,dep[x]);
    mk[x]=1;siz[x]=1;sm[dep[x]]++;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c]||bk[c])continue;
        dep[c]=dep[x]+1;
        dfs3(c);
        siz[x]+=siz[c];
    }
    mk[x]=0;
}
void dfs4(int x,int y){
    mk[x]=1;zx[x]=1e9;siz[x]=1;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c]||bk[c])continue;
        dfs4(c,y);
        siz[x]+=siz[c];
        zx[x]=min(zx[x],siz[c]);
    }
    zx[x]=min(zx[x],y-siz[x]);
    mk[x]=0;
    if(!rt||zx[rt]>zx[x])rt=x;
}
void dfs5(int x){
    mk[x]=1;mx=max(mx,dep[x]);jl[dep[x]]++;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c]||mk[c])continue;
        dep[c]=dep[x]+1;
        dfs5(c);
    }
    mk[x]=0;
}
void dfs6(int x){
    mk[x]=1;
    for(int i=0;i<g[x].size();i++){
        auto c=g[x][i];
        if(dep[x]>c.first)continue;
        rs[c.second]+=sm[min(c.first-dep[x],MX)]-jl[min(c.first-dep[x],mx)];
     //   cout<<x<<" "<<sm[min(c.first-dep[x],MX)]<<" "<<MX<<endl;
    }
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c]||mk[c])continue;
        dfs6(c);
    }
    mk[x]=0;
}
void solve(int x){
    if(siz[x]==1){
        for(int i=0;i<g[x].size();i++)rs[g[x][i].second]++;
        return;
    }
    bk[x]=1;MX=0;
    dep[x]=0;
    dfs3(x);
    for(int i=1;i<=MX;i++)sm[i]+=sm[i-1];
    for(int i=0;i<g[x].size();i++)rs[g[x][i].second]+=sm[min(g[x][i].first,MX)];
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c])continue;
        dep[c]=1;mx=0;
        dfs5(c);
        for(int j=1;j<=mx;j++)jl[j]+=jl[j-1];
       // cout<<"r"<<x<<endl;
        dfs6(c);
        for(int j=0;j<=mx;j++)jl[j]=0;
    }
    for(int i=0;i<=MX;i++)sm[i]=0;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c])continue;
        rt=0;
        dfs4(c,siz[c]);
        solve(rt);
    }
}
signed main(){
   // freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        p[x].push_back(y);
        p[y].push_back(x);
    }
    dfs1(1);
    dfs2(1,1);
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y,k,c;
        cin>>x>>y>>k;
        c=lca(x,y);
        g[c].push_back({k,i});
    }
    memset(mk,0,sizeof(mk));
    solve(1);
    for(int i=1;i<=m;i++)cout<<rs[i]<<"\n";
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 27672kb

input:

4988
1 2
1 3
1 4
4 5
1 6
3 7
3 8
5 9
4 10
6 11
3 12
9 13
11 14
8 15
11 16
1 17
7 18
8 19
18 20
7 21
10 22
15 23
18 24
4 25
24 26
9 27
23 28
3 29
3 30
30 31
11 32
18 33
2 34
32 35
29 36
29 37
19 38
9 39
6 40
25 41
16 42
31 43
6 44
42 45
32 46
27 47
32 48
44 49
7 50
10 51
24 52
46 53
30 54
46 55
39 56...

output:

2546
1004
4981
59
57
3369
3369
1004
4974
1719
59
171
4515
59
4952
4981
4974
1365
4981
1
1004
4780
4974
4974
1
13
4952
4515
59
4864
215
3369
472
1004
59
2546
472
131
13
4780
2546
13
13
4056
4952
171
4780
4974
13
171
13
59
59
1004
4981
3369
13
2546
57
13
4864
171
4952
59
4515
2087
1
4958
9
4056
3369
1...

result:

wrong answer 1st numbers differ - expected: '3226', found: '2546'

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 8
Accepted
time: 395ms
memory: 46172kb

input:

199995
1 2
2 3
2 4
1 5
3 6
5 7
6 8
4 9
2 10
5 11
5 12
1 13
1 14
1 15
13 16
1 17
10 18
16 19
11 20
8 21
17 22
4 23
19 24
7 25
22 26
8 27
14 28
1 29
9 30
3 31
3 32
21 33
19 34
26 35
34 36
5 37
29 38
22 39
5 40
13 41
28 42
8 43
35 44
22 45
14 46
12 47
32 48
11 49
8 50
18 51
23 52
18 53
4 54
6 55
10 56
...

output:

757
69428
2793
181264
91707
182
32496
199183
6399
15975
11640
119051
236
689
15
9532
41
36592
178936
56
45424
193403
90248
3417
949
68
34133
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199153
155706
196287
192862
53742
51862
179199
428
196282
199989
3613
26
99007
134461
198159
20382
7518...

result:

ok 199996 numbers

Test #10:

score: 0
Accepted
time: 231ms
memory: 44936kb

input:

199993
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

22
31743
62
30
510
6079
94
24063
190
4079
382
30
62
12159
1022
2043
8063
62
4
3063
4079
30
254
46
10
22
6111
12159
16127
22
1
12031
1
94
382
766
4063
254
46
766
1022
62
766
1
22
46
30
8063
8063
254
3063
22
62
30
1
62
254
4
10
15871
1022
46
2039
6079
22
254
1022
16127
30
766
8127
14
14
10
46
1
62
406...

result:

ok 199995 numbers

Test #11:

score: -8
Time Limit Exceeded

input:

199993
25163 125238
125238 19096
19096 88864
88864 113505
113505 12722
12722 56225
56225 8736
8736 74926
74926 38529
38529 80231
80231 19719
19719 198784
198784 75213
75213 190174
190174 163340
163340 62363
62363 144160
144160 130912
130912 3919
3919 21218
21218 85281
85281 187312
187312 79930
79930...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 329ms
memory: 45676kb

input:

199991
1 2
2 3
3 4
3 5
5 6
3 7
1 8
8 9
8 10
10 11
1 12
1 13
13 14
4 15
12 16
13 17
17 18
8 19
3 20
9 21
16 22
10 23
1 24
7 25
6 26
12 27
4 28
21 29
27 30
30 31
21 32
19 33
20 34
17 35
7 36
13 37
24 38
37 39
30 40
31 41
15 42
9 43
32 44
41 45
18 46
38 47
8 48
35 49
13 50
35 51
47 52
35 53
48 54
44 55...

output:

12
100250
189419
1417
83887
199124
1908
83887
17
4321
12
6
71
199516
1
181342
71
197305
197305
4321
169235
192649
20
189419
77114
71
195121
170566
109022
100
199516
86
12
194525
354
14548
109022
199516
354
152872
169235
197305
10704
38072
54937
181342
100250
71
11
354
181342
132537
10574
181342
1995...

result:

wrong answer 1st numbers differ - expected: '78', found: '12'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%