QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345122#5020. 举办乘凉州喵,举办乘凉州谢谢喵ANIG0 55ms27428kbC++143.1kb2024-03-06 09:48:292024-03-06 09:48:29

Judging History

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

  • [2024-03-06 09:48:29]
  • 评测
  • 测评结果:0
  • 用时:55ms
  • 内存:27428kb
  • [2024-03-06 09:48:29]
  • 提交

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,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){
    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;
        dfs3(c);
        dep[c]=dep[x]+1;
        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],n-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[c.first-dep[x]]-jl[c.first-dep[x]];
    }
    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)return;
    bk[x]=1;sm[0]=1;int MX=0;
    dep[x]=0;
    dfs3(x);
    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);
        dfs6(c);
        MX=max(MX,mx);
        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(){
    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});
        if(k==0)rs[i]=dep[x]+dep[y]-2*dep[c]+1;
    }
    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: 55ms
memory: 27428kb

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:

0
0
0
0
59
0
0
0
0
0
0
0
0
0
0
0
0
440
0
12
0
0
0
220
19
0
0
0
0
-8979
140
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
59
0
-8979
0
0
0
0
239
15
-4282
8
0
0
0
22
0
0
-8706
-1501
-7165
1317
0
-8835
0
-258
0
0
0
0
-348
16
0
19
0
0
0
12
220
0
-348
213
-8979
0
220
0
56
0
59
0
0
16
0
0
0
0
-36...

result:

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

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 0
Time Limit Exceeded

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:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #25:

score: 0
Time Limit Exceeded

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:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%