QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258624 | #6298. Coloring | SATSKY | RE | 0ms | 0kb | C++20 | 3.2kb | 2023-11-19 21:49:19 | 2023-11-19 21:49:19 |
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=max(dp[0][1][0],dp[0][2][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=6,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: 0
Runtime Error
input:
3 1 -1 -1 2 1 0 0 3 1 2