QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #153071 | #6826. Forest of Magic | qzez# | AC ✓ | 1220ms | 187572kb | C++14 | 3.0kb | 2023-08-29 10:38:31 | 2023-08-29 10:38:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e4+10,K=__lg(N)+2,lim=1e9,V=3e7,mod=1<<31;
int n,m,B,opt;
int dep[N],fa[K][N];
vector<int>to[N];
void init(int u){
dep[u]=dep[fa[0][u]]+1;
for(int v:to[u])if(v^fa[0][u]){
fa[0][v]=u,init(v);
}
}
int jump(int u,int x){
for(;x;x^=x&-x)u=fa[__builtin_ctz(x)][u];
return u;
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
u=jump(u,dep[u]-dep[v]);
if(u==v)return u;
for(int i=__lg(dep[u]);~i;i--)if(fa[i][u]^fa[i][v])u=fa[i][u],v=fa[i][v];
return fa[0][u];
}
bool chk(int u,int t){
return dep[u]>=dep[t]&&jump(u,dep[u]-dep[t])==t;
}
int calc(int u,int v,int t,int x){
if(dep[x]<=dep[t]){
return chk(t,x)?dep[u]+dep[v]-dep[t]-dep[fa[0][t]]:0;
}
if(chk(u,x))return dep[u]-dep[x]+1;
if(chk(v,x))return dep[v]-dep[x]+1;
return 0;
}
struct ops{
int u,v,c,k,t;
};
vector<ops>o,ot;
int k,root[N],ls[V],rs[V];
ll f[V],g[V];
void update(int &rt,int x,int y,ll z,int l=1,int r=lim){
ls[++k]=ls[rt],rs[k]=rs[rt],f[k]=f[rt],g[k]=g[rt],rt=k;
f[rt]+=y,g[rt]+=z;
if(l==r)return;
int mid=(l+r)>>1;
x<=mid?update(ls[rt],x,y,z,l,mid):update(rs[rt],x,y,z,mid+1,r);
}
void merge(int x,int y,int &z,int l=1,int r=lim){
if(!x||!y){
z=x|y;return;
}
f[z=++k]=f[x]+f[y],g[z]=g[x]+g[y];
if(l==r)return;
int mid=(l+r)>>1;
merge(ls[x],ls[y],ls[z],l,mid);
merge(rs[x],rs[y],rs[z],mid+1,r);
}
void query(int rt,int R,int x,ll &ans,int l=1,int r=lim){
if(!rt)return;
if(r<=R){
ans+=f[rt]*x+g[rt];return;
}
int mid=(l+r)>>1;
query(ls[rt],R,x,ans,l,mid);
if(mid<R)query(rs[rt],R,x,ans,mid+1,r);
}
struct opts{
int c,x;
ll y;
};
vector<opts>os[N];
void dfs(int u){
for(int v:to[u])if(v^fa[0][u]){
dfs(v),merge(root[u],root[v],root[u]);
}
for(opts x:os[u]){
update(root[u],x.c,x.x,x.y);
}
}
void rebuild(){
for(int i=1;i<=n;i++){
root[i]=0,os[i].clear();
}
k=0;
for(ops x:o)ot.push_back(x);
o.clear();
for(ops x:ot){
os[x.u].push_back({x.c,-x.k,(dep[x.u]+1ll)*x.k});
os[x.t].push_back({x.c,x.k,-(dep[x.t]+1ll)*x.k});
os[x.v].push_back({x.c,-x.k,(dep[x.v]+1ll)*x.k});
os[fa[0][x.t]].push_back({x.c,x.k,-1ll*dep[x.t]*x.k});
}
dfs(1);
}
int main(){
scanf("%d%d",&n,&m),opt=1;
B=sqrt(n*400);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
to[u].push_back(v),to[v].push_back(u);
}
init(1);
for(int i=1;i<K;i++)for(int u=1;u<=n;u++)fa[i][u]=fa[i-1][fa[i-1][u]];
int op;
for(ll u,v,c,k,ans=0;m--;){
scanf("%d%lld",&op,&u),u^=ans*opt;
if(op==1){
fa[0][++n]=u,dep[n]=dep[u]+1,to[u].push_back(n);
for(int i=1;i<K;i++)fa[i][n]=fa[i-1][fa[i-1][n]];
}else if(op==2){
scanf("%lld%lld%lld",&v,&c,&k),v^=ans*opt,c^=ans*opt,k^=ans*opt;
o.push_back({(int)u,(int)v,(int)c,(int)k,LCA(u,v)});
}else{
scanf("%lld",&c),c^=ans%mod*opt;
if(o.size()>B)rebuild();
ans=0,query(root[u],c,dep[u],ans);
for(ops x:o)if(x.c<=c){
ans+=1ll*calc(x.u,x.v,x.t,u)*x.k;
}
printf("%lld\n",ans);
ans%=mod;
}
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12272kb
input:
3 5 1 2 1 3 2 2 3 1 4 3 1 1 1 13 2 13 8 14 13 3 13 14
output:
12 14
result:
ok 2 number(s): "12 14"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8920kb
input:
100 116 2 1 3 2 1 4 5 3 2 6 7 5 8 4 9 4 10 2 8 11 9 12 13 6 11 14 5 15 16 6 1 17 1 18 11 19 20 9 21 15 22 21 9 23 12 24 25 10 26 14 16 27 13 28 29 6 17 30 31 13 17 32 25 33 34 12 23 35 36 15 37 5 32 38 39 38 28 40 41 32 42 34 43 5 14 44 44 45 22 46 47 17 6 48 49 29 50 45 12 51 26 52 53 45 54 21 55 1...
output:
0 0 0 18575924 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4605938 0 0 4605938 0 0 25367112 0 0 11598401 7040566 0 0 26267646
result:
ok 35 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 10956kb
input:
2000 288 2 1 3 1 4 1 5 1 6 3 3 7 1 8 6 9 10 7 11 6 2 12 5 13 14 5 2 15 4 16 17 8 18 8 19 15 20 10 21 16 10 22 21 23 24 18 25 23 26 12 27 10 28 7 29 7 21 30 18 31 20 32 33 15 34 2 29 35 36 11 37 24 38 32 10 39 30 40 41 36 42 39 19 43 23 44 36 45 13 46 8 47 38 48 27 49 48 50 37 51 52 30 53 2 54 3 43 5...
output:
0 0 0 0 0 0 0 2305240 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8951080 0 0 0 0 0 0 0 0 0 9421276 0 0 0 2305240 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20769550 0 0 0 0 0 0
result:
ok 84 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 10400kb
input:
5 1 1 2 3 1 4 1 5 4 1 2
output:
result:
ok 0 number(s): ""
Test #5:
score: 0
Accepted
time: 0ms
memory: 10744kb
input:
10 4 2 1 2 3 4 3 5 3 6 1 7 5 8 7 6 9 4 10 1 1 1 1 3 2 540904132 2 6 6 9973447 1324362
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1178ms
memory: 151524kb
input:
29579 97073 2 1 1 3 2 4 4 5 4 6 6 7 1 8 9 2 10 5 11 4 12 4 13 2 8 14 3 15 9 16 9 17 18 16 2 19 20 12 21 3 22 12 21 23 4 24 22 25 7 26 27 21 13 28 12 29 6 30 18 31 3 32 33 9 34 22 31 35 14 36 21 37 4 38 39 33 38 40 41 9 42 39 1 43 4 44 45 20 46 2 16 47 48 15 27 49 21 50 51 13 49 52 53 51 54 1 38 55 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 78256750 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22707642 0 8467566 0 0 0 0 0 0 0 0 0 15329702 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 38223 numbers
Test #7:
score: 0
Accepted
time: 1204ms
memory: 158796kb
input:
29952 99805 2 1 3 1 4 3 4 5 1 6 7 1 2 8 3 9 8 10 8 11 6 12 7 13 14 8 10 15 10 16 12 17 16 18 19 14 15 20 21 15 22 21 23 20 18 24 25 23 26 20 26 27 24 28 29 27 30 28 29 31 28 32 28 33 34 31 29 35 31 36 36 37 34 38 39 34 35 40 35 41 42 40 39 43 40 44 45 39 43 46 47 45 48 47 49 44 45 50 51 46 50 52 53 ...
output:
3606377445 0 0 0 0 0 0 0 127495141669 24141204114 0 0 0 97028567393 0 69029074275 0 0 0 37689049023 0 134562922691 0 0 0 86777476372 14583830482 0 0 0 119846447201 0 2408298450 209635762910 164836893177 0 0 0 0 0 0 0 229325093612 0 78643630463 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 77022904688 491481593729 2...
result:
ok 39673 numbers
Test #8:
score: 0
Accepted
time: 1175ms
memory: 156184kb
input:
29732 99402 2 1 1 3 3 4 5 3 6 4 7 4 8 3 5 9 6 10 11 7 12 10 13 9 14 11 15 13 12 16 14 17 18 13 19 17 18 20 16 21 22 19 17 23 19 24 21 25 26 20 24 27 25 28 25 29 30 29 31 25 32 28 33 28 34 33 35 31 36 31 37 35 38 37 38 39 37 40 38 41 39 42 41 43 44 38 45 42 41 46 43 47 48 42 49 46 50 46 45 51 52 50 5...
output:
0 466031225 466031225 0 466031225 0 0 0 20021393372 0 0 0 82119522352 0 0 0 0 0 0 0 0 0 480204445311 52758878606 0 0 0 0 0 0 32292491520 37066189420 0 0 0 52094313128 0 0 0 0 0 5365508117 0 293556576042 0 5355970109 0 0 0 0 0 76524851518 239082710554 0 0 0 561800459778 0 281888621989 0 0 47855594193...
result:
ok 39796 numbers
Test #9:
score: 0
Accepted
time: 669ms
memory: 143996kb
input:
29277 97122 2 1 3 1 1 4 5 1 1 6 7 1 1 8 9 1 10 1 11 1 1 12 1 13 1 14 15 1 1 16 17 1 1 18 1 19 20 1 1 21 1 22 1 23 1 24 25 1 1 26 1 27 28 1 1 29 1 30 1 31 32 1 1 33 34 1 1 35 1 36 37 1 1 38 39 1 40 1 1 41 42 1 1 43 1 44 45 1 46 1 1 47 1 48 1 49 1 50 51 1 52 1 53 1 54 1 55 1 1 56 57 1 58 1 59 1 1 60 6...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 38179 numbers
Test #10:
score: 0
Accepted
time: 683ms
memory: 145420kb
input:
30000 100000 2 1 3 1 1 4 5 1 6 1 7 1 8 1 9 1 1 10 1 11 12 1 13 1 14 1 15 1 1 16 1 17 18 1 19 1 20 1 21 1 1 22 23 1 1 24 25 1 1 26 27 1 28 1 29 1 1 30 1 31 1 32 1 33 34 1 35 1 36 1 1 37 38 1 39 1 1 40 1 41 42 1 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 51 1 52 1 53 1 1 54 1 55 1 56 57 1 1 58 59 1 60 1 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4405632 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 40096 numbers
Test #11:
score: 0
Accepted
time: 1220ms
memory: 135120kb
input:
29656 98742 14751 2485 14751 8895 8895 10992 5063 10992 5063 13797 13797 4340 10326 4340 16302 10326 16302 38 1390 38 1390 15785 14904 15785 14904 6961 9719 6961 9719 28490 11889 28490 11889 15439 249 15439 249 4552 2560 4552 2560 24449 24449 20296 20296 11446 14150 11446 14150 21676 23924 21676 239...
output:
0 31658265314 13063089260 121837417078 10767928080 121644843241 81447961371 0 188821292685 33306322370 172137903801 80733391591 551169395009 462317796974 84814999785 40811271852 602481061681 31553059226 51873429912 99060299026 32719093368 563421623451 246304578246 82812185229 158780399426 8180895670...
result:
ok 39164 numbers
Test #12:
score: 0
Accepted
time: 1184ms
memory: 138124kb
input:
30000 100000 10925 19663 10925 3184 3184 11108 11108 20568 8684 20568 8684 4695 28692 4695 19511 28692 19511 18086 11530 18086 13687 11530 15442 13687 15442 14155 4215 14155 4215 17955 19675 17955 7365 19675 7365 21210 10942 21210 10942 2801 2801 19197 16051 19197 16051 15617 17685 15617 17685 9083 ...
output:
0 0 0 39456609408 20945644840 9536609994 41644928962 144853169579 111321481013 126738998333 285590868908 0 620136763162 108755964826 177363659965 837644203271 316366256293 143979239413 202624730743 456311885800 1101193305255 97962293368 1256609585 0 800683279640 826351544094 1489275750018 1737742504...
result:
ok 39951 numbers
Test #13:
score: 0
Accepted
time: 1058ms
memory: 151856kb
input:
29909 99241 1 2 1 3 2 4 2 5 3 6 3 7 8 4 9 4 5 10 5 11 6 12 6 13 14 7 15 7 16 8 8 17 9 18 19 9 10 20 21 10 11 22 23 11 24 12 12 25 13 26 13 27 28 14 14 29 30 15 15 31 16 32 16 33 34 17 35 17 36 18 37 18 19 38 39 19 40 20 20 41 21 42 43 21 22 44 45 22 23 46 47 23 24 48 49 24 50 25 25 51 52 26 26 53 54...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7187118 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45145720 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 39358 numbers
Test #14:
score: 0
Accepted
time: 1054ms
memory: 155588kb
input:
29607 99516 2 1 3 1 4 2 2 5 3 6 3 7 8 4 9 4 5 10 11 5 6 12 6 13 14 7 7 15 8 16 17 8 9 18 9 19 10 20 21 10 11 22 23 11 12 24 12 25 26 13 13 27 28 14 14 29 30 15 15 31 32 16 33 16 17 34 35 17 18 36 18 37 38 19 39 19 40 20 41 20 42 21 21 43 22 44 22 45 46 23 47 23 24 48 49 24 50 25 25 51 26 52 26 53 54...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 991706 0 0 0 0 0 0 0 0 0 0 0 0 0 15325890 82802600 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 53841576 0 0 0 0 0 0 0 0 0 410498...
result:
ok 39527 numbers
Test #15:
score: 0
Accepted
time: 1032ms
memory: 187572kb
input:
29944 97708 2 1 2 3 4 3 4 5 5 6 6 7 8 7 9 8 9 10 11 10 11 12 12 13 14 13 15 14 16 15 17 16 17 18 19 18 20 19 20 21 21 22 23 22 24 23 25 24 26 25 27 26 27 28 28 29 30 29 30 31 31 32 32 33 34 33 35 34 36 35 36 37 38 37 38 39 39 40 41 40 42 41 43 42 44 43 44 45 46 45 46 47 47 48 49 48 49 50 50 51 52 51...
output:
4510290375 114070812445 6571934969 217910132343 6571934969 307559766492 188996268462 234123319862 693808941242 604761255610 863064525168 240085325266 174068203584 358004780723 686867199311 264855161128 826800986030 1664175437517 265074493584 1259982249654 2317588104085 227226953642 637901165501 3026...
result:
ok 27652 numbers
Test #16:
score: 0
Accepted
time: 1078ms
memory: 186856kb
input:
29537 99289 1 2 2 3 3 4 5 4 6 5 6 7 8 7 9 8 10 9 11 10 11 12 13 12 14 13 15 14 16 15 16 17 18 17 18 19 19 20 21 20 21 22 23 22 24 23 24 25 26 25 27 26 28 27 28 29 29 30 30 31 31 32 32 33 34 33 34 35 35 36 36 37 37 38 39 38 40 39 40 41 42 41 42 43 43 44 44 45 45 46 46 47 47 48 48 49 50 49 50 51 52 51...
output:
29107573 311684961780 143524688161 535163799690 67858987994 9563742 335829149416 771324943102 485786231940 1072918986682 1091608863260 252802048827 884084523974 490023481653 1086066997370 920516330969 1423246417014 106113830514 2324839633580 1313317608583 925973133936 1626093909545 2025826904052 740...
result:
ok 28826 numbers
Test #17:
score: 0
Accepted
time: 861ms
memory: 155556kb
input:
30000 100000 1 2 2 3 4 3 4 5 6 5 7 6 7 8 8 9 10 9 10 11 11 12 12 13 14 13 14 15 15 16 17 16 18 17 19 18 19 20 21 20 22 21 22 23 24 23 24 25 26 25 27 26 28 27 29 28 29 30 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 40 41 42 41 42 43 43 44 44 45 45 46 46 47 48 47 48 49 49 50 50 51 51 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4147263492166 171283485636 0 0 0 1803879803434 0 0 0 0 0 0 0 0 3173432451001 0 0 12271186786510 0 0 0 0 0 0 0 0 0 0 100319731618 0 0 0 0 200081336927 0 2900596570306 7432688746488 388594729933 0 0 0 0 0 1773278412 0 0 0 0 0 0 0 0 1845969941892 341157...
result:
ok 30000 numbers
Test #18:
score: 0
Accepted
time: 929ms
memory: 165444kb
input:
30000 100000 2 1 3 2 3 4 5 4 6 5 6 7 8 7 9 8 10 9 10 11 11 12 12 13 14 13 14 15 15 16 16 17 17 18 19 18 19 20 20 21 21 22 23 22 23 24 24 25 26 25 27 26 27 28 29 28 30 29 30 31 32 31 32 33 34 33 35 34 36 35 37 36 38 37 38 39 40 39 40 41 42 41 43 42 43 44 44 45 45 46 46 47 48 47 49 48 49 50 51 50 51 5...
output:
0 0 0 0 0 117462604990 0 0 0 2998548650146 0 0 1826771893306 0 0 0 0 0 0 0 4106373005521 0 0 0 0 0 0 5118784500443 1309291844260 0 0 0 0 5814472266352 0 0 842434114791 0 0 0 0 0 0 0 0 0 0 0 0 501874019149 0 0 0 0 0 0 0 0 0 0 0 0 27916772469990 0 0 0 0 0 6685083153128 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2766...
result:
ok 30000 numbers
Test #19:
score: 0
Accepted
time: 1ms
memory: 10432kb
input:
1 0
output:
result:
ok 0 number(s): ""