QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#540001#6298. Coloringchenxinyang2006WA 36ms199856kbC++202.9kb2024-08-31 16:13:222024-08-31 16:13:25

Judging History

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

  • [2024-08-31 16:13:25]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:199856kb
  • [2024-08-31 16:13:22]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,s;
int w[5005],cst[5005],a[5005];

int vis[5005];
vector <int> son[5005],sta,cir,_cir;
void init(){
	int p = s,q;
	while(!vis[p]){
		sta.eb(p);
		vis[p] = 1;
		p = a[p];
	}
	while(1){
		q = sta.back();
		vis[q] = 2;
		sta.pop_back();
		cir.eb(q);
		if(p == q) break;
	}	
	rep(u,1,n){
		if(vis[u] == 2) continue;
		son[a[u]].eb(u);
	}
}

int d[5005];
ll dp[5005][5005];
void dfs(int u){
	d[u] = 1;
	for(int v:son[u]){
		dfs(v);
		chkmax(d[u],d[v] + 1);
		ll Mx = -linf;
		rep(k,0,n){
			chkmax(Mx,dp[v][k]);
			dp[u][k] += Mx;
		}
	}
	if(u != s){
		rep(k,0,n){
			if(k % 2) dp[u][k] += w[u];
			dp[u][k] -= 1ll * cst[u] * k;
		}		
	}else{
		per(k,n - 1,0) dp[u][k] = dp[u][k + 1];
		rep(k,0,n){
			if(k % 2 == 0) dp[u][k] += w[u];
			dp[u][k] -= 1ll * cst[u] * k;
		}
	}
}

ll eval(int p,int k){
	if(k < 0) return -linf;
	return dp[cir[p]][k];
}

int main(){	
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d",&n,&s);
	rep(u,1,n) scanf("%d",&w[u]);
	rep(u,1,n) scanf("%d",&cst[u]);
	rep(u,1,n) scanf("%d",&a[u]);
	init();
	for(int u:cir) dfs(u);
	ll answer = -linf;
	if(vis[s] != 2){
		answer = max(dp[s][0],dp[s][1]);
		printf("%lld\n",answer);
		return 0;
	}
	int idx = -1;
	rep(k,0,SZ(cir) - 1) if(cir[k] == s) idx = k;
	rep(k,idx,SZ(cir) - 1) _cir.eb(cir[k]);
	rep(k,0,idx - 1) _cir.eb(cir[k]);
	cir = _cir;

	if(SZ(cir) == 1){
		printf("%lld\n",eval(0,0));
		return 0;
	}
	
	if(SZ(cir) == 2){
		chkmax(answer,eval(0,0) + eval(1,1));
		chkmax(answer,eval(0,0) + eval(1,0));
		chkmax(answer,eval(0,1) + eval(1,0));
		printf("%lld\n",answer);
		return 0;
	}
	ll v0,v1,v2;
	rep(i,0,n){
		v0 = eval(0,i) + eval(1,i - 1);
		v1 = eval(0,i) + eval(1,i);
		v2 = eval(0,i) + eval(1,i + 1);
		rep(k,2,SZ(cir) - 1){
			chkmax(v1,v2);
			chkmax(v0,v1);
			v0 += eval(k,i - 1);
			v1 += eval(k,i);
			v2 += eval(k,i + 1);
		}
		chkmax(answer,max(v0,v1));
		chkmax(answer,v2);
	}
	printf("%lld\n",answer);
	return 0;
}

詳細信息

Test #1:

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

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: 3980kb

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: 36ms
memory: 199856kb

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:

115528600061

result:

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