QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404067#6298. ColoringKevin090227WA 12ms199712kbC++205.2kb2024-05-03 10:53:522024-05-03 10:53:52

Judging History

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

  • [2024-05-03 10:53:52]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:199712kb
  • [2024-05-03 10:53:52]
  • 提交

answer

/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/#pragma GCC optimize(2,3,"Ofast","inline")
#include <bits/stdc++.h>/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
#define int long long/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
#define double long double/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
#define lowbit(i) (i&(-i))/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
#define mid ((l+r)>>1)/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
using namespace std;/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
int w[5005],p[5005],a[5005];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
int dp[5005][5005],siz[5005];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
int vis[5005],deg[5005],cyc[5005],m,rt,tmp[5005];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
vector<int> vc[5005],tr[5005],qq[5005];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
void dfs(int now,int fa){/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	for(auto v:tr[now]){/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		dfs(v,now);/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		for(int i=0;i<=siz[now]+siz[v];i++) tmp[i]=-1e18;/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		for(int i=0;i<=siz[now];i++) for(int j=0;j<=siz[v];j++) tmp[max(i,j)]=max(tmp[max(i,j)],dp[now][i]+dp[v][j]);/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		siz[now]+=siz[v];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		for(int i=0;i<=siz[now];i++) dp[now][i]=tmp[i];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	}/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	siz[now]++;/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	for(int i=siz[now];i>=1;i--) dp[now][i]=max(dp[now][i],dp[now][i-1]);/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	if(now!=rt) for(int i=0;i<=siz[now];i++) dp[now][i]+=w[now]*(i&1)-p[now]*i;/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	else for(int i=0;i<=siz[now];i++) dp[now][i]+=w[now]*(i&1);/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	// cout<<now<<" "; for(int i=0;i<=siz[now];i++) cout<<dp[now][i]<<" "; cout<<"\n";/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
}/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
signed main(){/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	int n,s; cin>>n>>s;/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=-1e18;/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	for(int i=1;i<=n;i++) cin>>w[i];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	for(int i=1;i<=n;i++) cin>>p[i];/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	for(int i=1;i<=n;i++) cin>>a[i],vc[i].push_back(a[i]),deg[a[i]]++,qq[a[i]].push_back(i);/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	queue<int> q; for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
	while(!q.empty()){/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		int f=q.front(); q.pop();/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		vis[f]=1;/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		for(auto v:vc[f]){/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
			deg[v]--;
			if(!deg[v]) q.push(v);/*qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq*/
		}
	}
	if(vis[s]){
		rt=s;
		dfs(s,0);
		cout<<max(max(dp[s][0],dp[s][2])-p[s],dp[s][1]);
		return 0;
	}
	int now=s;
	do{
		cyc[++m]=now;
		for(auto v:qq[now]){
			if(!vis[v]){
				now=v;
				break;
			}
		}
	}while(now!=s);
	for(int i=1;i<=n;i++) if(vis[i]) tr[a[i]].push_back(i);
	for(int i=1;i<=m;i++) rt=cyc[i],dfs(cyc[i],0);
	// for(int i=1;i<=m;i++) cout<<cyc[i]<<" "; cout<<"\n";
	dp[s][2]=max(dp[s][2],dp[s][0]),dp[s][0]=-1e18;
	for(int i=1;i<=m;i++){
		for(int j=2;j<=n;j++) dp[cyc[i]][j]=max(dp[cyc[i]][j],dp[cyc[i]][j-2]);
	}
	if(a[a[s]]!=s){
		int ans=-1e18;
		for(int i=1;i<=n;i++){
			int f[2]; f[0]=f[1]=0;
			for(int j=m;j>=1;j--){
				f[0]=f[0];
				f[1]=max(f[0],f[1]);
				if(j!=1) f[0]+=-p[cyc[j]]*(i-1)+dp[cyc[j]][i-1];
				if(j!=1) f[1]+=-p[cyc[j]]*i+dp[cyc[j]][i];
			}
			// cout<<max(f[0],f[1])+dp[cyc[1]][i]-p[cyc[1]]*(i-1)<<" "<<dp[cyc[1]][i]<<"\n";
			ans=max(ans,max(f[0],f[1])+dp[cyc[1]][i]-p[cyc[1]]*(i-1));
		}
		cout<<ans;
	}
	else{
		cout<<max(max(dp[s][1],max(dp[s][0],dp[s][2])-p[s]),dp[s][1]+dp[a[s]][1]-p[a[s]]);
	}
	return 0;
}

詳細信息

Test #1:

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

input:

3 1
-1 -1 2
1 0 0
3 1 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

10 8
36175808 53666444 14885614 -14507677 -92588511 52375931 -87106420 -7180697 -158326918 98234152
17550389 45695943 55459378 18577244 93218347 64719200 84319188 34410268 20911746 49221094
8 1 2 2 8 8 4 7 8 4

output:

35343360

result:

ok 1 number(s): "35343360"

Test #3:

score: -100
Wrong Answer
time: 12ms
memory: 199712kb

input:

5000 1451
531302480 400140870 -664321146 -376787089 -440627168 -672055995 924309614 2764785 -225700856 880835131 -435550509 162278080 -635253658 251803267 -499868931 213283508 603121701 -603347266 541062018 -502078443 -585620031 486788884 864390909 -670529282 -63580194 512939729 691685896 481123612 ...

output:

804501804

result:

wrong answer 1st numbers differ - expected: '83045140866', found: '804501804'