QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410753 | #7767. 数据结构 | ffffyc | 10 | 862ms | 249936kb | C++14 | 5.2kb | 2024-05-14 14:12:40 | 2024-05-14 14:12:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
namespace IO{//by cyffff
int len=0;
char ibuf[(1<<21)+1],*iS,*iT,out[(1<<26)+1];
#if ONLINE_JUDGE
#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline int read(){
reg char ch=gh();
reg int x=0;
reg char t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
return t?-x:x;
}
inline void putc(char ch){
out[len++]=ch;
}
template<class T>
inline void write(T x){
if(x<0)putc('-'),x=-x;
if(x>9)write(x/10);
out[len++]=x%10+48;
}
inline void flush(){
fwrite(out,1,len,stdout);
len=0;
}
inline char getc(){
char ch=gh();
while(ch<'a'||ch>'z') ch=gh();
return ch;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
#define vi vector<int>
#define vii vector<pii>
const int N=2e5+10,K=3+1;
int n,m,siz[N],fa[N],wm[N],dep[N],dfn[N],tp[N],tim;
vi ed[N],son[N];
vii sub[N],del[N][K],suk[N][K],ack[N][K],alk[N][K];
struct strBIT{
#define lowbit(i) (i&-i)
ull t1[N],t2[N];
inline void add(int x,ull v){
for(int i=x;i<=n;i+=lowbit(i))
t1[i]+=v,t2[i]+=x*v;
}
inline ull query(int x){
ull s1=0,s2=0;
for(int i=x;i;i-=lowbit(i))
s1+=t1[i],s2+=t2[i];
return (x+1)*s1-s2;
}
inline void add(int l,int r,int v){
add(l,v),add(r+1,-v);
}
inline ull query(int l,int r){
return query(r)-query(l-1);
}
}T;
inline int LCA(int x,int y){
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
x=fa[tp[x]];
}
return dep[x]<dep[y]?x:y;
}
inline void merge(vii &x,vii &y){
int n=x.size(),m=y.size();
if(!n){ x=y;return ; }
if(!m) return ;
for(auto tmp:y)
x.emplace_back(tmp);
// vii z;
// z.resize(n+m);
// merge(x.begin(),x.begin()+n,y.begin(),y.end(),z.begin());
// x=z;
}
inline void zip(vii &x){
if(!x.size()) return ;
sort(x.begin(),x.end());
vii y;
for(auto p:x){
if(y.size()&&y.back().sec+1==p.fir) y.back().sec=p.sec;
else y.push_back(p);
}
x=y;
}
inline void dfs1(int x,int f){
fa[x]=f,siz[x]=1,dep[x]=dep[f]+1;
for(int t:ed[x]){
if(t==f) continue;
son[x].push_back(t);
dfs1(t,x);
if(siz[t]>siz[wm[x]]) wm[x]=t;
siz[x]+=siz[t];
}
}
inline void dfs2(int x){
vi cn,ts;
for(int i=x;i;i=wm[i])
cn.push_back(i),tp[i]=x;
ts=cn;
for(int i=0;i<K;i++){
vi nt;
for(auto u:ts){
if(!dfn[u]) dfn[u]=++tim;
for(auto v:son[u])
nt.push_back(v);
}
ts=nt;
}
for(int u:cn)
for(int v:son[u])
if(v!=wm[u])
dfs2(v);
}
inline void dfs3(int x){
sub[x].emplace_back(mpr(dfn[x],dfn[x]));
suk[x][0].emplace_back(mpr(dfn[x],dfn[x]));
for(auto t:son[x]){
dfs3(t);
for(int i=1;i<K;i++)
merge(del[t][i],suk[x][i]),
merge(suk[x][i],suk[t][i-1]),
zip(suk[x][i]);
merge(sub[x],sub[t]);
}
vii rt[K];
for(int p=(int)son[x].size()-1;p>=0;p--){
int t=son[x][p];
del[t][0].emplace_back(mpr(dfn[x],dfn[x]));
for(int i=1;i<K;i++)
merge(del[t][i],rt[i]),
merge(rt[i],suk[t][i-1]),
zip(del[t][i]),zip(rt[i]);
}
zip(sub[x]);
for(int i=0;i<K;i++)
zip(suk[x][i]);
}
inline void dfs4(int x){
ack[x][0].emplace_back(mpr(dfn[x],dfn[x]));
for(int i=0;i<K;i++)
merge(ack[x][i],ack[fa[x]][i]),zip(ack[x][i]);
for(int i=0;i<K;i++){
alk[x][i]=suk[x][i];
if(i) merge(alk[x][i],alk[x][i-1]);
for(int j=1,las=x;j<=i&&las;j++,las=fa[las])
merge(alk[x][i],del[las][i-j]);
zip(alk[x][i]);
}
for(int t:son[x])
dfs4(t);
}
inline vii fdp1(int x,int y,int k){
vii p=ack[x][k],q=ack[y][k];
int n=p.size(),m=q.size();
vii t;
for(int i=0,l=0;i<n;i++){
int r=l-1;
while(r+1<m&&q[r+1].sec<=p[i].sec) r++;
int las=p[i].fir;
for(int j=l;j<=r;j++){
if(las<q[j].fir) t.push_back(mpr(las,q[j].fir-1));
las=q[j].sec+1;
}
if(las<=p[i].sec) t.push_back(mpr(las,p[i].sec));
l=r+1;
}
zip(t);
return t;
}
inline vii fdp2(int x,int y,int k){
int l=LCA(x,y);
vii t,p=fdp1(x,l,k),q=fdp1(y,l,k);
t.push_back(mpr(dfn[l],dfn[l]));
merge(t,p);
merge(t,q);
zip(t);
return t;
}
int main(){
n=read(),m=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
ed[u].push_back(v),ed[v].push_back(u);
}
dfs1(1,0),dfs2(1),dfs3(1),dfs4(1);
while(m--){
int opt=read();
if(opt==1){
int u=read(),v=read(),k=read(),w=read();
vii tmp=fdp2(u,v,k);
for(auto s:tmp)
T.add(s.fir,s.sec,w);
}else if(opt==2){
int u=read(),v=read();
for(auto s:sub[u])
T.add(s.fir,s.sec,v);
}else if(opt==3){
int u=read(),v=read(),k=read();
ull sum=0;
vii tmp=fdp2(u,v,k);
for(auto s:tmp)
sum+=T.query(s.fir,s.sec);
write(sum),putc('\n');
}else if(opt==4){
int u=read();
ull sum=0;
for(auto s:sub[u])
sum+=T.query(s.fir,s.sec);
write(sum),putc('\n');
}
}
flush();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 19ms
memory: 103372kb
input:
5000 5000 1 2 2 3 3 4 4 5 5 6 5 7 6 8 7 9 9 10 8 11 11 12 12 13 12 14 14 15 15 16 16 17 16 18 18 19 18 20 20 21 20 22 22 23 23 24 23 25 23 26 26 27 27 28 28 29 27 30 30 31 29 32 32 33 33 34 32 35 35 36 36 37 35 38 36 39 38 40 38 41 41 42 42 43 43 44 42 45 44 46 45 47 47 48 48 49 48 50 49 51 51 52 52...
output:
433472478 433472478 750774331896 0 433472478 749040441984 3840852828054 926043340 3709501531246 1674542130 2843103247896 1674542130 2601977518 4690957503188 492570862 7165490579666 492570862 1219355672 1300988759 2375568373686 985141724 4221137767 5059140822 1219355672 12945635936434 3104154008 1198...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '433472478'
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 742ms
memory: 224240kb
input:
200000 200000 1 2 1 3 1 4 3 5 1 6 1 7 7 8 8 9 2 10 1 11 5 12 1 13 7 14 10 15 2 16 7 17 11 18 5 19 5 20 1 21 16 22 1 23 3 24 20 25 14 26 2 27 6 28 15 29 10 30 15 31 5 32 13 33 12 34 31 35 31 36 36 37 36 38 1 39 28 40 5 41 12 42 41 43 20 44 30 45 22 46 11 47 47 48 45 49 14 50 41 51 3 52 30 53 29 54 6 ...
output:
0 0 0 0 0 0 0 0 7615073807 4176911055 0 4745654848 6222845818 0 0 9739142819 0 1424960716 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 15559673116 0 16391028892 0 15726757336 0 2421390...
result:
ok 100169 numbers
Test #4:
score: 0
Accepted
time: 862ms
memory: 233588kb
input:
200000 200000 121679 2 13340 3 45206 4 112138 5 47397 6 88216 7 173469 8 109861 9 58662 10 130056 11 61155 12 4313 13 196310 14 46189 15 32349 16 143798 17 103215 18 159921 19 27365 20 14332 21 49504 22 64451 23 106931 24 59878 25 177587 26 100555 27 86848 28 793 29 79845 30 150813 31 42854 32 11551...
output:
77900221111 0 0 476439705914 0 216029652830 0 0 631267909751 508097390689 0 29277716182 695169620128 0 809294022024 0 0 829507748883 260130797154 0 1005527232590 109198360548 821333235719 0 0 1265757368752 738460021055 296232170804 845184728833 0 434366813420 0 1922343637889 0 0 0 229703081048 0 441...
result:
ok 100073 numbers
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 276ms
memory: 249936kb
input:
200000 200000 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 ...
output:
0 38334494639998 26918248357976 0 172304962 38335340834863 38333731381809 91162210125204 122692368666653 123813915199077 116003080652000 174302868849461 0 78847551372657 28878647746523 292392954 3612480176 454579165096497 471741924281179 188849168018462 727682904 310663673748198 513701502045635 2923...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '38334494639998'
Subtask #4:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 594ms
memory: 224336kb
input:
200000 200000 1 2 2 3 3 4 1 5 3 6 5 7 5 8 7 9 2 10 7 11 11 12 10 13 6 14 3 15 14 16 4 17 11 18 3 19 14 20 4 21 4 22 12 23 18 24 5 25 5 26 14 27 13 28 24 29 11 30 26 31 29 32 28 33 31 34 23 35 33 36 6 37 11 38 22 39 13 40 35 41 37 42 21 43 12 44 4 45 16 46 12 47 21 48 1 49 26 50 45 51 41 52 46 53 7 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
wrong answer 259th numbers differ - expected: '782172417', found: '0'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #4:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%