QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#126751#6738. Covercsy2005AC ✓712ms173560kbC++143.5kb2023-07-18 22:28:392023-07-18 22:29:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 22:29:25]
  • 评测
  • 测评结果:AC
  • 用时:712ms
  • 内存:173560kb
  • [2023-07-18 22:28:39]
  • 提交

answer

#include <bits/stdc++.h>
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define spln(i,n) (i==n?'\n':' ')
using namespace std;
typedef long long i64;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
inline void read(i64 &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
int typ,_;
int n,m,i,j;
vector<int> bi[100005],v[100005];
int fa[100005],id[100005],sz[100005],tp[100005],son[100005],dfn[100005],ti,mp[100005],dep[100005];
int px[500005],py[500005],plca[500005],plx[500005],ply[500005];i64 pv[500005];

void dfs1(int x,int p)
{
	sz[x]=1;fa[x]=p;int c=0;
	if(p) bi[x].erase(find(bi[x].begin(),bi[x].end(),p));
	ff(bi[x],it){id[*it]=c++;dep[*it]=dep[x]+1;dfs1(*it,x);sz[x]+=sz[*it];if(!son[x]||sz[son[x]]<sz[*it])son[x]=*it;}
}
void dfs2(int x,int t)
{
	mp[dfn[x]=++ti]=x;tp[x]=t;
	if(son[x])dfs2(son[x],t);
	ff(bi[x],it)if(*it!=son[x])dfs2(*it,*it);
}
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 mp[min(dfn[x],dfn[y])];
}
int gtp(int x,int d)
{
	if(dep[x]<d) return x;
	while(dep[tp[x]]>d) x=fa[tp[x]];
	return mp[dfn[x]-(dep[x]-d)];
}

struct bit
{
	i64 s[500005];
	void add(int x,i64 c){while(x<=n) s[x]+=c,x+=(x&-x);}
	i64 query(int x){i64 c=0;while(x) c+=s[x],x&=(x-1);return c;}
}t1;
i64 query1(int x)
{
	i64 s=0;
	while(x){
		s+=t1.query(dfn[x])-t1.query(dfn[tp[x]]-1);
		x=fa[tp[x]];
	}
	return s;
}

vector<i64> f[100005];
i64 g[20][20],g0[20];
i64 h[100005];
void dfs3(int x)
{
//	cerr<<x<<": ";ff(bi[x],it)cerr<<*it<<' ';cerr<<endl;
	int i,j,k,len=bi[x].size();ff(bi[x],it) dfs3(*it);
	memset(g,0,sizeof(g));memset(g0,0,sizeof(g0));
	ff(bi[x],it){
		assert(id[*it]<=_);
		g0[id[*it]]=max(g0[id[*it]],f[*it].back());
	}
	ff(v[x],it){
		pv[*it]+=query1(px[*it])+(px[*it]==x?0:f[px[*it]].back());
		pv[*it]+=query1(py[*it])+(py[*it]==x?0:f[py[*it]].back());
		if(px[*it]==x){
			g0[id[ply[*it]]]=max(g0[id[ply[*it]]],pv[*it]);
		}
		else if(py[*it]==x){
			g0[id[plx[*it]]]=max(g0[id[plx[*it]]],pv[*it]);
		}
		else{
			g[id[plx[*it]]][id[ply[*it]]]=g[id[ply[*it]]][id[plx[*it]]]=max(g[id[plx[*it]]][id[ply[*it]]],pv[*it]);
		}
	}
	f[x].resize(1<<len);
	fz1(i,(1<<len)-1){
		j=len-1;while(!((i>>j)&1))j--;
		f[x][i]=max(f[x][i],f[x][i^(1<<j)]+g0[j]);
		fz0k(k,j)if((i>>k)&1) f[x][i]=max(f[x][i],f[x][i^(1<<j)^(1<<k)]+g[j][k]);
	}
	fz0k(i,len){
		h[bi[x][i]]=f[x][(1<<len)-1-(1<<i)];
		t1.add(dfn[bi[x][i]],h[bi[x][i]]);
	}
}
int main()
{
	read(n);read(m);read(_);fz1(i,n-1){int x,y;read(x);read(y);bi[x].push_back(y);bi[y].push_back(x);}
	int rt;fz1(i,n){assert(bi[i].size()<=_);if(bi[i].size()==1)rt=i;}
	dfs1(rt,0);dfs2(rt,rt);
	fz1(i,m) read(px[i]),read(py[i]),read(pv[i]),assert(px[i]!=py[i]),v[plca[i]=lca(px[i],py[i])].push_back(i),plx[i]=gtp(px[i],dep[plca[i]]+1),ply[i]=gtp(py[i],dep[plca[i]]+1);
	dfs3(rt);
	printf("%lld\n",f[rt].back());
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 25444kb

input:

5 7 3
1 2
1 3
2 4
2 5
3 2 8
5 4 10
3 1 2
1 2 7
2 1 2
1 2 1
5 2 3

output:

19

result:

ok 1 number(s): "19"

Test #2:

score: 0
Accepted
time: 654ms
memory: 173560kb

input:

100000 500000 12
2 1
3 2
4 2
5 2
6 5
7 2
8 5
9 3
10 2
11 2
12 5
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 12
25 2
26 2
27 2
28 2
29 2
30 15
31 30
32 23
33 26
34 22
35 30
36 26
37 3
38 3
39 3
40 3
41 3
42 3
43 3
44 3
45 3
46 3
47 20
48 21
49 4
50 4
51 4
52 4
53 4
54 4
55 4
56 4
57 4
5...

output:

660925834533

result:

ok 1 number(s): "660925834533"

Test #3:

score: 0
Accepted
time: 712ms
memory: 173480kb

input:

100000 500000 12
2 1
3 2
4 1
5 4
6 2
7 5
8 2
9 7
10 8
11 3
12 11
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 22
24 8
25 2
26 2
27 2
28 2
29 2
30 2
31 2
32 2
33 26
34 27
35 23
36 13
37 3
38 3
39 3
40 3
41 3
42 3
43 3
44 3
45 3
46 3
47 14
48 8
49 4
50 4
51 4
52 4
53 4
54 4
55 4
56 4
57 4
58 4...

output:

664434138007

result:

ok 1 number(s): "664434138007"

Test #4:

score: 0
Accepted
time: 691ms
memory: 173536kb

input:

100000 500000 12
2 1
3 1
4 2
5 3
6 4
7 2
8 7
9 2
10 6
11 4
12 8
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 13
24 23
25 2
26 2
27 2
28 2
29 2
30 2
31 2
32 2
33 26
34 31
35 33
36 33
37 3
38 3
39 3
40 3
41 3
42 3
43 3
44 3
45 3
46 3
47 34
48 16
49 4
50 4
51 4
52 4
53 4
54 4
55 4
56 4
57 4
58 ...

output:

639691495391

result:

ok 1 number(s): "639691495391"

Test #5:

score: 0
Accepted
time: 705ms
memory: 173424kb

input:

100000 500000 12
2 1
3 1
4 2
5 1
6 5
7 4
8 2
9 1
10 4
11 8
12 7
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 14
22 14
23 21
24 20
25 2
26 2
27 2
28 2
29 2
30 2
31 2
32 2
33 2
34 23
35 31
36 7
37 3
38 3
39 3
40 3
41 3
42 3
43 3
44 3
45 3
46 3
47 3
48 29
49 4
50 4
51 4
52 4
53 4
54 4
55 4
56 4
57 4
58 3...

output:

662244733768

result:

ok 1 number(s): "662244733768"

Test #6:

score: 0
Accepted
time: 694ms
memory: 171368kb

input:

100000 500000 12
2 1
3 1
4 1
5 1
6 3
7 1
8 4
9 3
10 7
11 2
12 5
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 14
21 12
22 11
23 9
24 20
25 2
26 2
27 2
28 2
29 2
30 2
31 2
32 2
33 2
34 2
35 14
36 30
37 3
38 3
39 3
40 3
41 3
42 3
43 3
44 3
45 3
46 24
47 38
48 35
49 4
50 4
51 4
52 4
53 4
54 4
55 4
56 4
57 4
58...

output:

669458090009

result:

ok 1 number(s): "669458090009"

Test #7:

score: 0
Accepted
time: 158ms
memory: 39624kb

input:

100000 500000 12
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 49
51 50
...

output:

488921502446

result:

ok 1 number(s): "488921502446"

Test #8:

score: 0
Accepted
time: 191ms
memory: 40564kb

input:

100000 500000 12
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 16
41 40
42 41
43 42
44 33
45 44
46 45
47 46
48 47
49 48
50 49
51 50
...

output:

468137226275

result:

ok 1 number(s): "468137226275"

Test #9:

score: 0
Accepted
time: 202ms
memory: 38360kb

input:

100000 500000 12
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 35
51 50
...

output:

483733769728

result:

ok 1 number(s): "483733769728"

Test #10:

score: 0
Accepted
time: 171ms
memory: 41256kb

input:

100000 500000 12
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 49
51 50
...

output:

478945297872

result:

ok 1 number(s): "478945297872"

Test #11:

score: 0
Accepted
time: 188ms
memory: 39544kb

input:

100000 500000 12
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 49
51 50
...

output:

489443708266

result:

ok 1 number(s): "489443708266"

Test #12:

score: 0
Accepted
time: 126ms
memory: 30904kb

input:

10000 500000 12
2 1
3 2
4 1
5 1
6 2
7 5
8 2
9 8
10 6
11 8
12 4
13 11
14 1
15 6
16 5
17 10
18 17
19 12
20 8
21 16
22 1
23 5
24 21
25 23
26 3
27 18
28 6
29 8
30 15
31 1
32 30
33 17
34 23
35 5
36 24
37 33
38 25
39 34
40 1
41 24
42 11
43 6
44 18
45 28
46 25
47 32
48 40
49 29
50 43
51 33
52 9
53 2
54 20
...

output:

560772428222

result:

ok 1 number(s): "560772428222"

Test #13:

score: 0
Accepted
time: 145ms
memory: 32212kb

input:

10000 500000 12
2 1
3 2
4 2
5 2
6 4
7 5
8 4
9 4
10 4
11 4
12 10
13 5
14 13
15 9
16 15
17 2
18 5
19 14
20 11
21 11
22 20
23 20
24 1
25 5
26 15
27 20
28 17
29 4
30 18
31 12
32 14
33 18
34 18
35 16
36 31
37 18
38 19
39 12
40 17
41 14
42 7
43 27
44 25
45 13
46 35
47 10
48 15
49 46
50 44
51 21
52 15
53 2...

output:

572767352204

result:

ok 1 number(s): "572767352204"

Test #14:

score: 0
Accepted
time: 134ms
memory: 31552kb

input:

10000 500000 12
2 1
3 1
4 2
5 2
6 2
7 4
8 7
9 7
10 2
11 9
12 3
13 1
14 7
15 9
16 8
17 2
18 13
19 12
20 2
21 16
22 8
23 13
24 8
25 20
26 25
27 14
28 4
29 28
30 4
31 12
32 13
33 24
34 1
35 21
36 5
37 16
38 28
39 35
40 28
41 13
42 20
43 19
44 16
45 40
46 28
47 3
48 5
49 14
50 2
51 4
52 47
53 47
54 15
5...

output:

585482767864

result:

ok 1 number(s): "585482767864"

Test #15:

score: 0
Accepted
time: 151ms
memory: 31976kb

input:

10000 500000 12
2 1
3 2
4 3
5 3
6 3
7 5
8 7
9 4
10 3
11 2
12 7
13 4
14 8
15 9
16 1
17 12
18 13
19 2
20 3
21 16
22 10
23 20
24 4
25 19
26 6
27 17
28 5
29 17
30 27
31 22
32 14
33 11
34 4
35 24
36 34
37 14
38 23
39 18
40 30
41 28
42 36
43 12
44 5
45 14
46 17
47 11
48 14
49 16
50 16
51 18
52 30
53 17
54...

output:

564574799774

result:

ok 1 number(s): "564574799774"

Test #16:

score: 0
Accepted
time: 150ms
memory: 32192kb

input:

10000 500000 12
2 1
3 1
4 2
5 2
6 4
7 6
8 5
9 8
10 7
11 7
12 5
13 1
14 5
15 11
16 9
17 3
18 4
19 10
20 8
21 2
22 11
23 18
24 10
25 8
26 16
27 22
28 11
29 20
30 12
31 4
32 19
33 27
34 6
35 1
36 24
37 18
38 30
39 32
40 10
41 9
42 15
43 34
44 27
45 34
46 7
47 34
48 39
49 32
50 13
51 11
52 38
53 17
54 5...

output:

575291114848

result:

ok 1 number(s): "575291114848"