QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#669101#5020. 举办乘凉州喵，举办乘凉州谢谢喵byron100000 0ms0kbC++176.4kb2024-10-23 17:16:442024-10-23 17:17:10

Judging History

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

  • [2024-10-23 17:17:10]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：0kb
查看
  • [2024-10-23 17:16:44]
  • 提交

answer

#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define _UN using namespace
using namespace std;
const int MAXN=2e5+10,INF=1e9+10;
int n,qn; vector<int> G[MAXN];
long ans[MAXN];
int siz[MAXN],son[MAXN],dep[MAXN],fa[MAXN],top[MAXN],dfn[MAXN],dfnc;
namespace S0{
void dfs1(int u,int fa_){
    fa[u]=fa_,siz[u]=1,dep[u]=dep[fa_]+1;
    for(int v:G[u]){
        if(v==fa_) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int top_){
    dfn[u]=++dfnc,top[u]=top_;
    if(son[u]) dfs2(son[u],top_);
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
        else v=fa[top[v]];
    }
    return dep[u]<dep[v]?u:v;
}
int find_(int t,int u){
    assert(u!=t);
    int lst=-1;
    while(top[u]!=top[t]) lst=top[u],u=fa[top[u]];
    return t==u?lst:son[t];
}
} using S0::lca; using S0::find_;
struct Qt1{ int d,id; }; vector<Qt1> Q1[MAXN];
struct Qt2{ int d,id,op; }; vector<Qt2> Q2[MAXN]; // Query F
struct Qt3{ int d,id,op; }; vector<Qt3> Q3[MAXN]; // Query G
void add_qry(int u,int v,int d,int id){
    Q3[fa[u]].push_back({d,id,-1}),Q3[v].push_back({d,id,1});
    int lst=0;
    while(top[v]!=top[u]){
        if(son[v]) Q2[son[v]].push_back({d-1,id,1});
        if(lst) Q2[lst].push_back({d-1,id,-1});
        v=fa[top[v]];
    }
}
namespace S1{
struct BIT{
    int A[MAXN];
    vector<int> mdf;
    void upd(int i,int x){
        for(i++; i<=n+1; i+=i&-i) A[i]+=x;
        mdf.push_back(i);
    }
    int qry(int i){
        int ret=0;
        for(i++; i; i-=i&-i) ret+=A[i];
        return ret;
    }
    void reset(){
        for(int i0:mdf){
            for(int i=i0+1; i<=n+1; i+=i&-i) A[i]=0;
        }
        mdf.clear();
    }
} bit;
int siz[MAXN],dep[MAXN],bel[MAXN]; bool vis[MAXN];
void dfs2(int u,int fa,int totsz,pair<int,int>& rt){ // find root
    siz[u]=1;
    int mxsz=0;
    for(int v:G[u]){
        if(v==fa||vis[v]) continue;
        dfs2(v,u,totsz,rt);
        siz[u]+=siz[v];
        mxsz=max(mxsz,siz[v]);
    }
    mxsz=max(mxsz,totsz-siz[u]);
    rt=min(rt,pair<int,int>{mxsz,u});
}
void dfs1(int u,int fa){
    siz[u]=1;
    for(int v:G[u]){
        if(v!=fa) dep[v]=dep[u]+1,dfs1(v,u);
    }
}
void dfs3(int u,int fa){
    bit.upd(dep[u],1);
    for(int v:G[u]){
        if(v==fa||vis[v]) continue;
        dfs3(v,u);
    }
}
void dfs4(int u,int fa,int op){
    for(auto q:Q1[u]){
        if(q.d>=dep[u]) ans[q.id]+=op*bit.qry(q.d-dep[u]);
    }
    for(int v:G[u]){
        if(v==fa||vis[v]) continue;
        dfs4(v,u,op);
    }
}
vector<int> S1[MAXN];
void solve(int r){
    vis[r]=1,dep[r]=0;
    dfs1(r, 0);
    dfs3(r,0),dfs4(r,0,1);
    bit.reset();
    for(int v:G[r]){
        if(vis[v]) continue;
        dfs3(v,r),dfs4(v,r,-1);
        bit.reset();
    }
    for(int v:G[r]){
        if(vis[v]) continue;
        pair<int,int> rt {INF,0};
        dfs2(v,0,siz[v],rt);
        solve(rt.second);
    }
}
void main(){
    pair<int,int> rt {INF,0};
    dfs2(1,0,n,rt);
    solve(rt.second);
}
}
namespace S2{
struct SGT{
#define ls (T[u].ls_)
#define rs (T[u].rs_)
#define mid ((l+r)/2)
    struct{ int ls_,rs_,cnt; } T[MAXN*20]; int nnd;
    void ins(int& u,int l,int r,int i){
        if(!u) u=++nnd;
        T[u].cnt++;
        if(l==r) return;
        i<=mid ? ins(ls,l,mid,i) : ins(rs,mid+1,r,i);
    }
    void pushup(int u){ T[u].cnt=T[ls].cnt+T[rs].cnt; }
    int qry(int u,int l,int r,int qr){
        if(r<=qr) return T[u].cnt;
        return qry(ls,l,mid,qr)+(mid<qr?qry(rs,mid+1,r,qr):0);
    }
    int merge(int u,int v,int l,int r){
        if(!u||!v) return u|v;
        if(l==r){ T[u].cnt+=T[v].cnt; return u; }
        ls=merge(ls,T[v].ls_,l,mid),rs=merge(rs,T[v].rs_,mid+1,r);
        pushup(u);
        return u;
    }
#undef ls
#undef rs
#undef mid
} sgt;
int rt[MAXN];
void dfs(int u){
    sgt.ins(rt[u],1,n,dep[u]);
    for(int v:G[u]){
        if(v!=fa[u]) dfs(v),rt[u]=sgt.merge(rt[u],rt[v],1,n);
    }
    for(auto q:Q2[u]) ans[q.id]+=q.op*sgt.qry(rt[u],1,n,q.d+dep[u]);
}
void main(){ dfs(1); }
}
namespace S3{
struct BIT{
    int A[MAXN];
    void upd(int i,int x){
        for(i++; i<=n+1; i+=i&-i) A[i]+=x;
    }
    int qry(int i){
        int ret=0;
        for(i++; i; i-=i&-i) ret+=A[i];
        return ret;
    }
} bit;
void dfs2(int u,int d,int op){
    bit.upd(dep[u]-d,op);
    for(int v:G[u]){
        if(v!=fa[u]) dfs2(v,d,op);
    }
}
void dfs1(int u){
    bit.upd(0,1);
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[u]) dfs2(v,dep[u],1);
    }
    for(auto q:Q3[u]) ans[q.id]+=q.op*bit.qry(q.d);
    for(int v:G[u]){
        if(v==fa[u]) continue;
        dfs1(v);
    }
    bit.upd(0,-1);
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[u]) dfs2(v,dep[u],-1);
    }
}
void main(){ dfs1(1); }
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
    freopen("future.in","r",stdin);
    freopen("future.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    RNG(_,1,n-1,u,v) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
    S0::dfs1(1,0),S0::dfs2(1,1);
    cin>>qn;
    RNG(i,1,qn){
        int u,v,d; cin>>u>>v>>d;
        if(d==0){
            int t=lca(u,v);
            ans[u]=dep[u]+dep[v]-2*dep[t]+1;
            continue;
        }
        if(dfn[u]>dfn[v]) swap(u,v);
        if(u==v) Q1[u].push_back({d,i});
        else if(dfn[v]<dfn[u]+siz[u]){
            int v1=find_(u,v);
            Q1[u].push_back({d,i}),Q2[v1].push_back({d-1,i,-1});
            add_qry(u,v1,d,i);
        }else{
            int t=lca(u,v),u1=find_(t,u),v1=find_(t,v);
            Q1[t].push_back({d,i}),Q2[u1].push_back({d-1,i,-1}),Q2[v1].push_back({d-1,i,-1});
            add_qry(t,u1,d,i),add_qry(t,v1,d,i);
        }
    }
    S1::main();
    S2::main();
    S3::main();
    RNG(i,1,qn) cout<<ans[i]<<"\n";
}
源文件, 语言: C++17

详细

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

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:

result:

Subtask #2:

score: 0
Dangerous Syscalls

Test #9:

score: 0
Dangerous Syscalls

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
Dangerous Syscalls

Test #25:

score: 0
Dangerous Syscalls

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%
English 繁體中文 简体中文

服务器时间: 2024-12-05 05:19:48 | 开源项目