結果

問題 No.1927 AB-CD
ユーザー vjudge1
提出日時 2024-10-24 21:35:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,636 bytes
コンパイル時間 11,407 ms
コンパイル使用メモリ 183,260 KB
実行使用メモリ 96,436 KB
最終ジャッジ日時 2024-10-24 21:36:15
合計ジャッジ時間 15,919 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 2 TLE * 1
other WA * 4 RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=33*33*33*33;
int n,m,q,cntb,cnt,fr[4],deg[N],dfn[N],low[N],bel[N],pri[]={0,2,3,5,7,11,13,17,19,23,27,29,31},num[33][33];
ll f[N],val[N],valb[N];
bool vis[N],ex[N];
stack<int> stk;
unordered_map<ll,bool> mp;
string s,t;
vector<int> a[N],b[N];
int id(int a,int b,int c,int d)
{
int t=n+1;
return a*t*t*t+b*t*t+c*t+d;
}
ll q_pow(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1)
ret=ret*a;
a=a*a;
b>>=1;
}
return ret;
}
void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
stk.push(u);
vis[u]=true;
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++cntb;
int v;
do
{
v=stk.top();
stk.pop();
vis[v]=false;
bel[v]=cntb;
}while(v!=u);
}
}
void topo()
{
queue<int> que;
for(int i=1;i<=cntb;i++)
if(!deg[i])
que.push(i);
while(!que.empty())
{
int u=que.front();
que.pop();
f[u]+=valb[u];
for(int i=0;i<b[u].size();i++)
{
int v=b[u][i];
f[v]=max(f[v],f[u]);
deg[v]--;
if(deg[v]==0)
que.push(v);
}
}
ll ans=0;
for(int i=1;i<=cntb;i++)
ans=max(ans,f[i]);
cout<<ans;
}
void init()
{
q=(n+1)*(n+1)*(n+1)*(n+1);
for(int i=2;i<=n;i++)
{
int u=i;
for(int j=1;j<=12;j++)
{
while(u%pri[j]==0)
u/=pri[j],num[i][j]++;
num[i][j]+=num[i-1][j];
}
}
for(int ka=0;ka<=n;ka++)
{
for(int kb=0;ka+kb<=n;kb++)
{
for(int kc=0;ka+kb+kc<=n;kc++)
{
int kd=n-ka-kb-kc;
int uid=id(ka,kb,kc,kd);
val[uid]=1;
for(int j=1;j<=12;j++)
val[uid]*=q_pow(pri[j],num[n][j]-num[ka][j]-num[kb][j]-num[kc][j]-num[kd][j]);
}
}
}
}
int main()
{
cin>>n>>m;
init();
for(int i=1;i<=m;i++)
{
cin>>s>>t;
if(s==t)
continue;
memset(fr,0,sizeof(fr));
for(int j=0;j<s.length();j++)
fr[s[j]-'A']--;
for(int j=0;j<t.length();j++)
fr[t[j]-'A']++;
for(int ka=max(0,-fr[0]);ka<=n;ka++)
for(int kb=max(0,-fr[1]);ka+kb<=n;kb++)
for(int kc=max(0,-fr[2]);ka+kb+kc<=n;kc++)
{
int kd=n-ka-kb-kc;
if(kd+fr[3]<0)
continue;
int uid=id(ka,kb,kc,kd),vid=id(ka+fr[0],kb+fr[1],kc+fr[2],kd+fr[3]);
a[uid].push_back(vid);
ex[uid]=ex[vid]=true;
}
}
for(int i=0;i<q;i++)
if(!dfn[i]&&ex[i])
tarjan(i);
for(int i=0;i<q;i++)
{
if(!ex[i])
continue;
int u=bel[i];
valb[u]+=val[i];
for(int j=0;j<a[i].size();j++)
{
int v=bel[a[i][j]];
ll tid=1ll*min(u,v)*q+max(u,v);
if(!mp[tid]&&u!=v)
{
mp[tid]=true;
b[u].push_back(v);
deg[v]++;
}
}
}
topo();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0