QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258621#6298. ColoringSATSKYWA 15ms200308kbC++203.2kb2023-11-19 21:43:362023-11-19 21:43:36

Judging History

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

  • [2023-11-19 21:43:36]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:200308kb
  • [2023-11-19 21:43:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;const int M=998244353;const double eps=1e-10;const ll inf=1e17;
bool o=0;
struct S
{
	vector<int>fa,cov,ring;
	vector<ll>w,c;
	vector<vector<int>>es;
	vector<vector<ll>>dres;
	vector<vector<vector<ll>>>dp;//ring_pos/lay_cnt/drop_cnt
	int n,S,rlen;
	void ini()
	{
		fa.resize(n+1);w.resize(n+1);c.resize(n+1);es.resize(n+1);cov.resize(n+1,0);
		dres.resize(n+1,vector<ll>(n+1));
	}
	void findring()
	{
		int x,cnt=n+10;
		for(x=S;!cov[x];cov[x]=1,x=fa[x],ring.push_back(x));

		//cout<<x<<"|"<<S<<'\n';for(auto k:ring)cout<<k<<"_";cout<<'\n';

		if(x!=S)ring.clear(),ring.push_back(S);reverse(ring.begin(),ring.end());
		cov.assign(n+1,0);for(auto k:ring)cov[k]=1;
		if(o)
		{
			cout<<"siz:"<<int(ring.size())<<'|';
			cout<<ring[0]<<"?"<<ring.back()<<'\n';
			cout<<S<<"&"<<x<<'\n';
		}
		rlen=ring.size();if(o){cout<<"ring_siz:"<<rlen<<'\n';}
	}
	void spr(int x)
	{
		for(int i=0;i<=n;i++)dres[x][i]=w[x]*(i&1)-c[x]*i;
		for(auto k:es[x])if(!cov[k]) { cov[k]=1,spr(k);ll mx=0;for(int i=0;i<=n;i++)mx=max(mx,dres[k][i]),dres[x][i]+=mx; }
		if(o)
		{
			cout<<x<<":val:"<<w[x]<<" cost:"<<c[x]<<" fa:"<<fa[x]<<'\n';
			cout<<"dres:";for(auto kk:dres[x])cout<<kk<<'_';cout<<'\n';
			cout<<"***\n";
		}
	}
	void solve()
	{
		cin>>n>>S;ini();for(int i=1;i<=n;i++)cin>>w[i];for(int i=1;i<=n;i++)cin>>c[i];
		for(int i=1;i<=n;i++)cin>>fa[i],es[fa[i]].push_back(i);
		findring();for(auto k:ring)spr(k);
		//cout<<"ring_siz:"<<rlen<<'\n';for(auto k:ring)cout<<k<<'_';cout<<'\n';
		dp.resize(2,vector<vector<ll>>(n+1,vector<ll>(3,-inf)));
		for(int i=0,sw=((rlen-1)&1);i<=n;i++)
		{
			dp[sw][i][0]=dres[ring.back()][i];
			if(o)cout<<rlen-1<<'/'<<ring.back()<<":pos"<<i<<" drop:"<<0<<":"<<dp[sw][i][0]<<'\n';
		}
		for(int i=rlen-2,sw=(i&1);i>=0;i--,sw^=1)
		{
			dp[sw].assign(n+1,vector<ll>(3,-inf));
			for(int a=0;a<=n;a++)
			{
				for(int b=a;b>=max(0,a-2);b--)for(int c=b;c>=max(0,a-2);c--)
					dp[sw][a][a-c]=max(dp[sw][a][a-c],dp[sw^1][b][b-c]);
				for(int e=0;e<3;e++)
				{
					dp[sw][a][e]+=dres[ring[i]][a];
					if(o)cout<<i<<'/'<<ring[i]<<":pos"<<a<<" drop:"<<e<<":"<<dp[sw][a][e]<<'\n';
				}
			}
		}
		ll res=-inf;
		//if(rlen<=2){cout<<"0\n";return;}
		if(rlen==1)res=dp[0][1][0];
		else if(rlen==2)res=max(dp[0][2][2],max(dp[0][1][0],dp[0][1][1]));
		else for(int i=1;i<=n;i++)for(int e=0;e<3;e++)res=max(res,dp[0][i][e]);
		cout<<res+c[S]<<"\n";
	}
};
void precal()
{

}
void presta()
{
	srand(time(0));int n=4,S=rand()%n+1;	
	cout<<n<<' '<<S<<'\n';
	for(int i=1;i<=n;i++)cout<<rand()%20-10<<' ';cout<<'\n';
	for(int i=1;i<=n;i++)cout<<rand()%10<<' ';cout<<'\n';
	for(int i=1;i<=n;i++)
	{
		int x=i;while(x==i)x=rand()%n+1;cout<<x<<' ';
	}
	cout<<'\n';	
}
int main()
{
	//freopen("1.in","r",stdin);
	bool p=0;
	if(p)
	{
		freopen("2.in","w",stdout);
		presta();
	}
	else
	{
		//freopen("2.in","r",stdin);
		//freopen("2.in","r",stdin);
		//cout<<fixed<<setprecision(12);
		ios::sync_with_stdio(0);cin.tie(0);precal();
		int t=1;//cin>>t;
		//clock_t a=clock();
		while(t--) { S SS;SS.solve(); }
	}
	
	//cout<<"Time:"<<double(clock()-a)<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

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: 0ms
memory: 3740kb

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: 15ms
memory: 200308kb

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:

80519799290

result:

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