QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#540001 | #6298. Coloring | chenxinyang2006 | WA | 36ms | 199856kb | C++20 | 2.9kb | 2024-08-31 16:13:22 | 2024-08-31 16:13:25 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'