QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167419#6738. CoverPhantomThresholdAC ✓950ms145720kbC++203.2kb2023-09-07 14:32:122023-09-07 14:32:12

Judging History

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

  • [2023-09-07 14:32:12]
  • 评测
  • 测评结果:AC
  • 用时:950ms
  • 内存:145720kb
  • [2023-09-07 14:32:12]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;

const int maxn = 100005;
const int maxm = 500005;
const int maxd = 18;
const int mask = 1<<11;
inline void up(int &a,const int &b){ if(a<b)a=b; }

int n,m,K;
vector<int>V[maxn];
int fa[maxn][maxd],dep[maxn],d[maxn];

void dfs(const int x)
{
	for(int i=1;i<maxd;i++) fa[x][i]=fa[ fa[x][i-1] ][i-1];
	for(auto y:V[x]) if(y!=fa[x][0])
	{
		d[x]++;
		dep[y]=dep[x]+1;
		fa[y][0]=x;
		dfs(y);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=maxd-1;i>=0;i--) if(dep[x]-dep[y]>=(1<<i))
		x=fa[x][i];
	if(x==y) return x;
	for(int i=maxd-1;i>=0;i--) if(fa[x][i]!=fa[y][i])
		x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int kthfa(int x,int k)
{
	for(int i=maxd-1;i>=0;i--) if(k>=(1<<i))
		x=fa[x][i],k-=(1<<i);
	return x;
}

int ty[maxm],ec[maxm];
vector<int>pr[maxm];

vector<int>Va[maxn],Vb[maxn];
int cnt,val[maxm<<1];
vector< int >S[maxn]; int flag[maxn];

int yid[20],yy[maxn];
int f[mask],g[maxn];
int ad1[20],ad2[20][20];
void dp(const int x)
{
	for(auto y:V[x]) if(y!=fa[x][0])
		dp(y);
	
	{
		int idx=0;
		for(auto y:V[x]) if(y!=fa[x][0])
		{
			yid[idx]= y;
			yy[y]=idx;
			idx++;
		}
	}
	
	for(int i=0;i<d[x];i++) 
	{
		ad1[i]=0;
		for(int j=0;j<d[x];j++) 
			ad2[i][j]=0;
	}
	for(auto i:Vb[x])
	{
		if(pr[i].size()==1)
		{
			int u=pr[i][0], ui=yy[u];
			up( ad1[ui], ec[i] + val[i<<1]+flag[u] );
		}
		else
		{
			int u=pr[i][0], ui=yy[u];
			int v=pr[i][1], vi=yy[v];
			up( ad2[ui][vi], ec[i] + val[i<<1]+flag[u] + val[i<<1|1]+flag[v] );
			up( ad2[vi][ui], ec[i] + val[i<<1]+flag[u] + val[i<<1|1]+flag[v] );
		}
	}
	for(int i=0;i<d[x];i++)
	{
		up( ad1[i], g[yid[i]] );
	}
	
	memset(f,0,sizeof f);
	int uS = 1<<d[x];
	//f[x][0]=0;
	for(int s=1;s<uS;s++)
	{
		int yi=31-__builtin_clz(s);
		
		up(f[s], f[s^(1<<yi)]+ad1[yi]);
		
		for(int j=0;j<yi;j++) if(s>>j&1)
		{
			up(f[s], f[s^1<<yi^1<<j]+ad2[yi][j]);
		}
		
	}
	
	int idx=0;
	for(auto y:V[x]) if(y!=fa[x][0])
	{
		flag[y]+= f[(uS-1)^1<<idx];
		
		if( S[x].size()<S[y].size() )
			swap(S[x],S[y]),swap(flag[x],flag[y]);
		
		for(auto i:S[y])
		{
			val[i]+= flag[y]-flag[x];
			S[x].push_back( i );
		}
		
		idx++;
	}
	
	g[x]=f[uS-1];
	for(auto i:Va[x])
	{
		val[i]= g[x]-flag[x];
		S[x].push_back( i );
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m>>K;
	for(int i=1;i<n;i++)
	{
		int x,y; cin>>x>>y;
		V[x].push_back(y);
		V[y].push_back(x);
	}
	
	dep[1]=1; dfs(1);
	
	for(int i=1;i<=m;i++)
	{
		int ai,bi,wi; cin>>ai>>bi>>wi;
		ec[i]=wi;
		int ff=lca(ai,bi);
		if(ff==ai || ff==bi)
		{
			ty[i]=1;
			Vb[ff].push_back(i);
			if(ai!=ff)
			{
				Va[ai].push_back(i<<1);
				pr[i].push_back(kthfa(ai,dep[ai]-dep[ff]-1));
			}
			else
			{
				Va[bi].push_back(i<<1);
				pr[i].push_back(kthfa(bi,dep[bi]-dep[ff]-1));
			}
		}
		else
		{
			ty[i]=2;
			Vb[ff].push_back(i);
			
			Va[ai].push_back(i<<1);
			pr[i].push_back(kthfa(ai,dep[ai]-dep[ff]-1));
			Va[bi].push_back(i<<1|1);
			pr[i].push_back(kthfa(bi,dep[bi]-dep[ff]-1));
		}
	}
	
	dp(1);
	cout<<g[1]<<endl;
	
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 37436kb

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: 925ms
memory: 143532kb

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: 950ms
memory: 144976kb

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: 919ms
memory: 143104kb

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: 901ms
memory: 144760kb

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: 943ms
memory: 145720kb

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: 583ms
memory: 122784kb

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: 496ms
memory: 129992kb

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: 540ms
memory: 127612kb

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: 565ms
memory: 125256kb

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: 559ms
memory: 119752kb

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: 246ms
memory: 117340kb

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: 239ms
memory: 120344kb

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: 239ms
memory: 114788kb

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: 212ms
memory: 115124kb

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: 250ms
memory: 117072kb

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"