QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258545 | #6298. Coloring | SATSKY | WA | 12ms | 394968kb | C++20 | 2.9kb | 2023-11-19 19:53:16 | 2023-11-19 19:53:17 |
Judging History
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;
struct S
{
vector<int>fa,cov,ring;
vector<ll>w,c;
vector<vector<int>>es;
vector<vector<ll>>dres,dprem;
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));dprem.resize(n+1,vector<ll>(n+1));
}
void findring()
{
int x,cnt=n+10;
for(x=fa[S];cnt&&x!=S;x=fa[x],cnt--)ring.push_back(x);
if(n==5000&&0)
{
cout<<"siz:"<<int(ring.size())<<'|';
cout<<ring[0]<<"?"<<ring.back()<<'\n';
cout<<S<<"&"<<x<<'\n';
int tc=0;
for(auto k:ring)
{
cout<<k<<'_';tc++;
if(tc%40==0)cout<<'\n';
}
}
if(cnt==-1)ring.clear();ring.push_back(x);reverse(ring.begin(),ring.end());
}
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]){spr(k);for(int i=0;i<=n;i++)dres[x][i]+=dprem[k][i];}
dprem[x][0]=0;for(int i=1;i<=n;i++)dprem[x][i]=max(dprem[x][i-1],dres[x][i]);
//cout<<x<<":val:"<<w[x]<<" cost:"<<c[x]<<" fa:"<<fa[x]<<'\n';
//cout<<"dres:";for(auto kk:dres[x])cout<<kk<<'_';cout<<'\n';
//cout<<"dprem:";for(auto kk:dprem[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();rlen=ring.size();
cov.assign(n+1,0);for(auto k:ring)cov[k]=1;
//for(auto k:ring)cout<<k<<"_";cout<<'\n';
if(n==5000)return;
for(auto k:ring)spr(k);
/*
for(auto k:ring)
{
cout<<k<<":\n";
cout<<"dres:";for(auto kk:dres[k])cout<<kk<<'_';cout<<'\n';
cout<<"dprem:";for(auto kk:dprem[k])cout<<kk<<'_';cout<<'\n';
}
*/
dp.resize(rlen,vector<vector<ll>>(n+1,vector<ll>(3,-inf)));
for(int i=0;i<=n;i++)dp[rlen-1][i][0]=dres[ring.back()][i];
for(int i=rlen-2;i>=0;i--)
{
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[i][a][a-c]=max(dp[i][a][a-c],dp[i+1][b][b-c]);
}
}
for(int e=0;e<3;e++)
{
dp[i][a][e]+=dres[ring[i]][a];
//cout<<i<<'/'<<ring[i]<<":pos"<<a<<" drop:"<<e<<":"<<dp[i][a][e]<<'\n';
}
}
}
ll res=-inf;
//if(rlen<=1){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()
{
}
int main()
{
//freopen("1.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: 1ms
memory: 3540kb
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: 3504kb
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: 394968kb
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:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements