結果
問題 | No.1927 AB-CD |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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();}