QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#410102#5020. 举办乘凉州喵,举办乘凉州谢谢喵grass8cow0 718ms135828kbC++174.5kb2024-05-13 12:50:332024-05-13 12:50:34

Judging History

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

  • [2024-05-13 12:50:34]
  • 评测
  • 测评结果:0
  • 用时:718ms
  • 内存:135828kb
  • [2024-05-13 12:50:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
#define pb push_back
const int N=2e5+10;
vector<int>g[N];
namespace Dia{
    bool vis[N];
    int di[25][N],F[N],dk[N];
    int ae[N*25];
    int al[N],ar[N],bl[N],br[N],cn;
    int sz[N],rt,Mx,S;
    void df(int x,int f){
        sz[x]=1;int mm=-1;
        for(int v:g[x])
            if(v!=f&&!vis[v])df(v,x),mm=max(mm,sz[v]),sz[x]+=sz[v];
        mm=max(mm,S-sz[x]);if(mm<Mx)Mx=mm,rt=x;
    }
    int T1[N],T2[N],md1,md2;
    int O,oe;
    void dfs2(int x,int d,int f){
        oe++;
        di[O][x]=d;
        while(md1<d)md1++,T1[md1]=0;
        while(md2<d)md2++,T2[md2]=0;
        T1[d]++,T2[d]++;
        for(int v:g[x])
            if(v!=f&&!vis[v])dfs2(v,d+1,x),sz[x]+=sz[v];
    }
    int fz[N];
    void sol(int x){
        vis[x]=1,O=dk[x];
        T1[0]=(x<=n),md1=0;
        for(int v:g[x])if(!vis[v]){
            T2[0]=0,md2=0;
            oe=0,dfs2(v,1,0);
            for(int i=1;i<=md2;i++)T2[i]+=T2[i-1];
            S=oe,Mx=S+1,df(v,0);
            F[rt]=x,dk[rt]=dk[x]+1,fz[v]=rt;
            bl[rt]=cn+1,br[rt]=cn+md2+1;
            for(int i=0;i<=md2;i++)ae[++cn]=T2[i];
        }
        for(int i=1;i<=md1;i++)T1[i]+=T1[i-1];
        al[x]=cn+1,ar[x]=cn+md1+1;
        for(int i=0;i<=md1;i++)ae[++cn]=T1[i];
        for(int v:g[x])if(!vis[v])sol(fz[v]);
    }
    int oi[N],fp[N];
    int Ask(int x,int d){
        if(d<0)return 0;
        int u=x,su=0,nx=0;
        while(u){
            int oi=di[dk[u]][x];
            if(oi<=d){
                su+=ae[min(ar[u],al[u]+d-oi)];
                if(nx)su-=ae[min(br[nx],bl[nx]+d-oi)];
            }
            nx=u,u=F[u];
        }
        return su;
    }
    void build(){
        oe=cn=0;
        for(int i=1;i<=n;i++)T1[i]=T2[i]=oi[i]=fp[i]=dk[i]=ae[i]=al[i]=ar[i]=bl[i]=br[i]=F[i]=dk[i]=0,vis[i]=0;
        S=n,Mx=n+1,df(1,0),sol(rt);
    }
}
int sz[201000],son[201000],dfn[201000],top[200100],db[200100],bel[200100],fa[201000],d[201000];
void dfs(int x){
    sz[x]=1;int mm=-1;
    for(int v:g[x])if(v!=fa[x]){
        fa[v]=x,d[v]=d[x]+1,dfs(v);
        if(mm<sz[v])mm=sz[v],son[x]=v;
sz[x]+=sz[v];
    }
}
void dfs2(int x,int ff){
    bel[dfn[x]=++dfn[0]]=x,top[x]=ff;
    if(!son[x]){db[x]=x;return;}
    dfs2(son[x],ff),db[x]=db[son[x]];
    for(int v:g[x])if(v!=fa[x]&&v!=son[x])dfs2(v,v);
}
int lca(int u,int v){
    if(top[u]!=top[v]){
        if(d[top[u]]<d[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    if(d[u]>d[v])swap(u,v);return u;
}
struct BIT{
    int tr[201000];
    bool vis[201000];
    int sta[200100],top;
    inline void ad(int x,int z){
        for(x++;x<=n+1;x+=(x&-x)){
            if(!vis[x])vis[x]=1,sta[++top]=x;
            tr[x]+=z;
        }
    }
    inline int ask(int x){
        if(x<0)return 0;
        x=min(x,n);
        int s=0;
        for(x++;x;x-=(x&-x))s+=tr[x];
        return s;
    }
    inline void cl(){
        while(top)vis[sta[top]]=0,tr[sta[top]]=0,top--;
    }
}T;
int ans[200100];
vector<array<int,3> >G[200100];
void sg(int u,int d,int id,int z){
    while(u)
        G[u].pb({d,id,z}),u=fa[top[u]];
}
void sol(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)g[i].clear(),sz[i]=son[i]=dfn[i]=top[i]=db[i]=bel[i]=fa[i]=d[i]=0,G[i].clear();
    for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].pb(v),g[v].pb(u);
    Dia::build();
    dfn[0]=0,dfs(1),dfs2(1,1);
    int q;
    scanf("%d",&q);
    for(int i=1,u,v,d;i<=q;i++){
        scanf("%d%d%d",&u,&v,&d);
        int lc=lca(u,v);
        ans[i]=Dia::Ask(lc,d);
        sg(u,d,i,1),sg(v,d,i,1),sg(lc,d,i,-2);
    }
    for(int t=1;t<=n;t++)if(top[t]==t){
        for(int j=dfn[t];j<=dfn[db[t]];j++){
            int u=bel[j];
            T.ad(0,1),T.ad(d[u]-d[t]+1,-1);
            if(son[u]){
                for(int k=dfn[son[u]]+sz[son[u]];k<dfn[u]+sz[u];k++){
                    int z=d[bel[k]]-d[u];
                    T.ad(z,1),T.ad(z+1+(d[u]-d[t]),-1);
                }
            }
            for(auto it:G[u])ans[it[1]]+=T.ask(it[0])*it[2];
        }
        T.cl();
        for(int j=dfn[db[t]];j>dfn[t];j--){
            int u=bel[j];
            T.ad(d[u]-d[t],1);
            if(son[u]){for(int k=dfn[son[u]]+sz[son[u]];k<dfn[u]+sz[u];k++)T.ad(d[bel[k]]-d[t],1);}
            for(auto it:G[fa[u]])
            ans[it[1]]+=(T.ask(it[0]+(d[u]-d[t]-1))-T.ask(it[0]-1))*it[2];
        }
        T.cl();
    }
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
int main(){
    int T=1;while(T--)sol();
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 43040kb

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:

371
60
2856
98
12
611
611
106
3397
361
76
61
1124
-12
3371
2877
4100
219
4197
4
189
1030
4083
4032
5
11
1730
723
-10
2017
132
923
116
161
5
680
-96
76
28
1769
493
2
45
513
2341
144
1823
2330
9
-91
30
14
27
197
4522
555
21
64
-7
7
3980
5
4516
28
2172
278
5
2593
10
1575
372
27
877
-116
-23
2183
157
21...

result:

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

Subtask #2:

score: 0
Runtime Error

Test #9:

score: 8
Accepted
time: 622ms
memory: 106996kb

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: 8
Accepted
time: 617ms
memory: 135828kb

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
Accepted
time: 718ms
memory: 91156kb

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:

97095
57496
116181
132482
144412
69917
174677
96334
37980
80902
148979
22074
166530
153392
43419
163281
148526
62703
79363
199993
153733
152298
5085
156125
117973
61925
36346
95741
124148
102890
20093
5408
77598
176994
177809
169850
144418
43786
189237
69098
5167
199993
103575
105198
197612
38829
20...

result:

ok 199994 numbers

Test #12:

score: 0
Runtime Error

input:

200000
3219 118490
118490 61372
61372 74390
74390 88375
88375 63918
63918 37580
37580 33219
33219 170480
170480 81737
81737 153202
153202 93921
93921 149109
149109 88339
88339 167037
167037 67099
67099 58363
58363 6784
6784 109386
109386 11895
11895 14872
14872 65638
65638 43958
43958 181669
181669 ...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 694ms
memory: 105280kb

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:

21
16469
63960
1949
7706
124400
1917
21763
36
1283
-9
11
214
140956
3
26334
20
87750
114381
4019
3334
62609
23
9559
2440
245
98852
26612
362
-12
137081
-123
32
66988
273
-3354
25433
170026
89
28878
28794
95663
1998
6657
10178
57319
9549
251
27
578
8194
12015
648
85899
154255
319
15733
13714
16
79968...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%