QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410753#7767. 数据结构ffffyc10 862ms249936kbC++145.2kb2024-05-14 14:12:402024-05-14 14:12:40

Judging History

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

  • [2024-05-14 14:12:40]
  • 评测
  • 测评结果:10
  • 用时:862ms
  • 内存:249936kb
  • [2024-05-14 14:12:40]
  • 提交

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%