QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167353#6738. CoverPhantomThresholdWA 864ms142988kbC++203.6kb2023-09-07 14:03:272023-09-07 14:03:27

Judging History

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

  • [2023-09-07 14:03:27]
  • 评测
  • 测评结果:WA
  • 用时:864ms
  • 内存:142988kb
  • [2023-09-07 14:03:27]
  • 提交

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];
	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]);
		}
		
	/*	for(auto i:Vb[x])
		{
			if(pr[i].size()==1)
			{
				int u=pr[i][0], ui=yy[u];
				if(s>>ui&1)
					up(f[s], f[s^1<<ui]+);
			}
			else
			{
				int u=pr[i][0], ui=yy[u];
				int v=pr[i][1], vi=yy[v];
				if( (s>>ui&1) && (s>>vi&1) )
					up(f[s], f[s^1<<ui^1<<vi]+ec[i] + val[i<<1]+flag[u] + val[i<<1|1]+flag[v]);
			}
		}*/
	}
	
	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: 1ms
memory: 35140kb

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: -100
Wrong Answer
time: 864ms
memory: 142988kb

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:

491616561283

result:

wrong answer 1st numbers differ - expected: '660925834533', found: '491616561283'