QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#670134 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | byron10000 | 7 | 1253ms | 42584kb | C++14 | 6.4kb | 2024-10-23 20:36:34 | 2024-10-23 20:36:35 |
Judging History
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(true){
if(son[v]) Q2[son[v]].push_back({d-1,id,1});
if(lst) Q2[lst].push_back({d-1,id,-1});
if(top[u]==top[v]) break;
lst=top[v],v=fa[top[v]];
}
}
namespace S1{
struct BIT{
int A[MAXN];
vector<int> mdf;
void upd(int i,int x){
mdf.push_back(i);
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;
}
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[i]=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(v1,v,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(u1,u,d,i),add_qry(v1,v,d,i);
}
}
S1::main();
S2::main();
S3::main();
RNG(i,1,qn) cout<<ans[i]<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 728ms
memory: 40108kb
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:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 4974 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 49...
result:
ok 4966 numbers
Test #2:
score: 7
Accepted
time: 371ms
memory: 42584kb
input:
4914 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 27 ...
output:
3378 4914 231 4914 4914 3378 22 4914 4914 2559 4914 75 219 1407 1138 863 24 3890 4914 4914 399 399 13 139 77 4914 4095 3071 4914 23 151 110 1407 43 54 4914 4914 1919 2559 77 735 3071 24 133 479 4914 33 831 4 4914 4914 79 4914 199 3890 3071 73 567 15 75 21 126 4914 4914 203 4914 75 127 62 41 4914 409...
result:
ok 4975 numbers
Test #3:
score: 7
Accepted
time: 1252ms
memory: 42092kb
input:
4921 1151 2767 2767 322 322 4451 4451 4867 4867 1265 1265 3197 3197 3890 3890 1052 1052 1407 1407 1578 1578 566 566 2965 2965 260 260 4908 4908 308 308 553 553 2845 2845 4249 4249 1284 1284 73 73 1088 1088 277 277 1878 1878 4128 4128 3609 3609 2126 2126 149 149 3467 3467 1653 1653 4913 4913 3604 360...
output:
4921 3192 3260 3983 949 2080 605 3471 4901 2020 2552 1570 3325 3643 458 1296 3072 3423 3045 2569 1720 3195 1908 4397 1536 2799 3072 2443 3176 3311 1403 1119 842 3028 2387 1903 2303 4921 2149 1974 4153 2053 2888 2344 3264 3709 3443 3601 2571 1207 4519 3745 959 1920 1305 1706 1743 522 1266 2153 1812 1...
result:
ok 4930 numbers
Test #4:
score: 7
Accepted
time: 1124ms
memory: 41812kb
input:
4942 877 4180 4180 4409 4409 2233 2233 3491 3491 3459 3459 4501 4501 2192 2192 3539 3539 4379 4379 4346 4346 1553 1553 2100 2100 3426 3426 3461 3461 811 811 2981 2981 1493 1493 610 610 599 599 1741 1741 3216 3216 1646 1646 1016 1016 3757 3757 2570 2570 2900 2900 4649 4649 1014 1014 538 538 4288 4288...
output:
4236 3338 4942 4942 4942 4942 1551 1272 3885 4140 4942 3627 3132 3991 3157 4024 4942 4942 3761 3064 238 4942 4942 4942 4942 4942 2256 4942 649 4496 4942 4942 4491 866 4208 4942 4942 4726 4942 4462 4942 4942 4234 2676 2593 4942 4088 4942 2704 3344 3560 4942 4942 4461 4511 4634 3437 2884 3842 4942 494...
result:
ok 4910 numbers
Test #5:
score: 7
Accepted
time: 1054ms
memory: 38412kb
input:
4996 1 2 2 3 1 4 4 5 4 6 3 7 4 8 8 9 3 10 9 11 5 12 7 13 12 14 8 15 8 16 14 17 10 18 15 19 17 20 15 21 19 22 21 23 14 24 20 25 25 26 21 27 20 28 19 29 29 30 24 31 31 32 29 33 27 34 34 35 31 36 27 37 30 38 35 39 38 40 37 41 34 42 41 43 43 44 42 45 36 46 37 47 47 48 47 49 41 50 50 51 46 52 50 53 51 54...
output:
4869 3419 3000 4640 4996 4996 3854 4165 4542 4996 1758 3584 3011 4996 4996 4383 2064 4199 2786 2470 4759 4996 4657 4157 2443 2594 1823 3215 1635 3908 1903 3207 2153 4448 4996 4996 3071 2649 3452 4996 1235 1599 2732 2244 2311 4618 1250 4577 3498 4941 1058 3498 3539 3415 907 4170 4996 4144 2235 2664 4...
result:
ok 4952 numbers
Test #6:
score: 7
Accepted
time: 764ms
memory: 41984kb
input:
4935 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50 5...
output:
4442 4133 346 3268 4850 3512 3312 3581 4092 4655 2256 3950 3157 3480 4935 4188 4935 1593 1135 4935 4935 4875 4108 3771 4158 4935 4935 3156 3148 1814 4935 3368 4303 2861 4917 2370 3992 4764 2772 4935 4935 2640 4935 4691 2291 4268 1798 4530 3058 3219 4935 3141 4935 2699 4547 2164 2495 3049 370 3409 21...
result:
ok 4992 numbers
Test #7:
score: 7
Accepted
time: 320ms
memory: 37800kb
input:
4919 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
2653 3219 4302 1418 1713 713 3341 647 487 1508 971 4851 4443 3078 2380 2267 4171 18 2056 1833 3136 817 4375 4103 3423 433 3967 725 282 2358 4171 1680 3350 2403 802 1855 137 2091 3731 1061 581 1273 4783 133 1911 4239 4233 678 3127 3481 284 1896 435 593 4781 103 4647 1615 1231 2689 574 1833 4783 645 4...
result:
ok 4980 numbers
Test #8:
score: 7
Accepted
time: 1253ms
memory: 42328kb
input:
4973 1 4517 2 744 3 1115 4 3191 5 4186 6 4608 7 3898 8 3939 9 1998 10 2287 11 2277 12 4200 13 4935 14 3955 15 3683 16 278 17 547 18 3351 19 2642 20 4050 21 3457 22 2337 23 3435 24 1476 25 4853 26 3985 27 736 28 3016 29 4840 30 3866 31 4567 32 4067 33 3724 34 1872 35 1533 36 4787 37 53 38 1632 39 295...
output:
91 2487 2646 1791 2447 3327 532 1801 1079 1526 1236 77 4028 3401 4103 1573 3540 1641 452 52 2497 3128 2593 734 1293 3213 1786 1626 2130 2033 1935 2673 1758 1838 1284 758 2952 301 947 2875 3073 1462 2615 2842 3561 1969 1416 3088 2476 1082 696 3665 2041 3263 3063 2988 1402 1050 2967 3696 2309 3767 281...
result:
ok 4982 numbers
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
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #33:
score: 0
Time Limit Exceeded
input:
49994 1 2 1 3 1 4 4 5 4 6 2 7 5 8 2 9 5 10 3 11 11 12 5 13 2 14 5 15 14 16 15 17 15 18 11 19 7 20 2 21 1 22 21 23 15 24 22 25 16 26 22 27 16 28 11 29 17 30 21 31 3 32 22 33 3 34 33 35 34 36 17 37 22 38 21 39 22 40 11 41 14 42 30 43 42 44 27 45 41 46 21 47 5 48 17 49 40 50 31 51 23 52 40 53 17 54 39 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%