結果

問題 No.1927 AB-CD
ユーザー vjudge1vjudge1
提出日時 2024-10-24 21:35:58
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 WA -
testcase_28 WA -
testcase_29 TLE -
権限があれば一括ダウンロードができます

ソースコード

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();
}
0