ABC求助memset的替代物

RT，上周六晚复建打ABC 很快做完了ABCDEF，但是为什么我D挂了呢？我写的O（(n+m)k）自认为复杂度非常正确，一看只T一个点，妈妈耶为啥这个复杂度sample1会跑2200ms？于是开始反复检查反复优化，甚至从TLE变成WA，最终拼尽全力无法战胜D题，赛时无比绝望。赛后一看题解：我这不是写的完全正确吗？于是继续愤而卡常，仍然是拼尽全力无法战胜。

直到我万念俱灰开始比对AC代码，然后发现了罪魁祸首:memset清空dp 删去这一句之后直接从2200ms->60ms

我真的吐了

这次是因为实现所以恰好不用dp清空，删去没有问题，但是若下次需要进行清空的情况下请问有什么可以替代的方式吗？

附代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
vector<int>e[maxn];
int pos[maxn][20];
void dfs(int x,int k)//xianshou win1 houshou win 2
{
	for(int i=0;i<e[x].size();i++)
	{
		if(pos[e[x][i]][k-1]==2)
		{
			pos[x][k]=1;
			return;
		}
	}
	pos[x][k]=2;
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		int n,m,k;
		cin>>n>>m>>k;
		string s;
		cin>>s;
		for(int i=1;i<=n;i++)
			e[i].clear();
    //这里本有句memset
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			e[x].push_back(y);
		}
		for(int i=1;i<=n;i++)
			if(s[i-1]=='A')
				pos[i][0]=1;
			else
				pos[i][0]=2;
		for(int i=1;i<=2*k;i++)
			for(int x=1;x<=n;x++)
				dfs(x,i);
		if(pos[1][2*k]==1)
			cout<<"Alice"<<endl;
		else
			cout<<"Bob"<<endl;
	}
	return 0;
}

ABC求助memset的替代物

讨论操作

回复

相关推荐

ABC求助memset的替代物