QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#482986#7669. Maze ReductionNahidameowTL 0ms0kbC++205.1kb2024-07-18 08:43:072024-07-18 08:43:08

Judging History

你现在查看的是最新测评结果

  • [2024-07-18 08:43:08]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-18 08:43:07]
  • 提交

answer

#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=2e5+10;
const int mod=998244353;
typedef unsigned U;
const int M=998244353;
struct ModInt{
	static constexpr U mod=M;
	U val;
	constexpr ModInt():val(0U){}
	constexpr ModInt(U _val):val(_val){}
	constexpr ModInt(int _val):val((_val%int(mod)+int(mod))%int(mod)){}
	constexpr ModInt(ll _val):val((_val%ll(mod)+ll(mod))%ll(mod)){}
	ModInt(const ModInt &P):val(P.val){}
	inline ModInt operator +(ModInt p){return ModInt(int(val)+int(p.val));}
	inline ModInt operator -(ModInt p){return ModInt(int(val)-int(p.val));}
	inline ModInt operator *(ModInt p){return ModInt(1ll*val*p.val);}
	inline ModInt QP(ll y){
		if(y<0)return inv().QP(-y);
		ModInt A=(*this),B=1U;
		for(;y;A=A*A,y>>=1)if(y&1)B=B*A;
		return B;
	}inline ModInt inv(){return QP(mod-2);}
	inline ModInt operator /(ModInt p){return (*this)*p.inv();}
	inline ModInt operator ^(ModInt p){return QP(p.val);}
	template<typename T>
	inline ModInt operator ^(T p){return QP(p);}

	template<typename T>
	inline ModInt operator +(T p){return (*this)+ModInt(p);}
	template<typename T>
	inline ModInt operator -(T p){return (*this)-ModInt(p);}
	template<typename T>
	inline ModInt operator *(T p){return (*this)*ModInt(p);}
	template<typename T>
	inline ModInt operator /(T p){return (*this)/ModInt(p);}

	inline ModInt operator +(){return (*this);}
	inline ModInt operator -(){return ModInt(0)-(*this);}

	template<typename T>
	inline friend ModInt operator +(T A,ModInt P){return ModInt(A)+P;}
	template<typename T>
	inline friend ModInt operator -(T A,ModInt P){return ModInt(A)-P;}
	template<typename T>
	inline friend ModInt operator *(T A,ModInt P){return ModInt(A)*P;}
	template<typename T>
	inline friend ModInt operator /(T A,ModInt P){return ModInt(A)/P;}

	inline void operator --(){val=(!val?mod-1:val-1);}
	inline void operator ++(){val=(val==mod-1?0:val+1);}

	inline void operator +=(ModInt P){(*this)=(*this)+P;}
	inline void operator -=(ModInt P){(*this)=(*this)-P;}
	inline void operator *=(ModInt P){(*this)=(*this)*P;}
	inline void operator /=(ModInt P){(*this)=(*this)/P;}

	template<typename T>
	inline void operator +=(T P){return (*this)=(*this)+ModInt(P);}
	template<typename T>
	inline void operator -=(T P){return (*this)=(*this)-ModInt(P);}
	template<typename T>
	inline void operator *=(T P){return (*this)=(*this)*ModInt(P);}
	template<typename T>
	inline void operator /=(T P){return (*this)=(*this)/ModInt(P);}
	template<typename T>
	inline void operator ^=(T P){return (*this)=(*this)^P;}

	U key(){return val;}
	inline bool operator == (ModInt P){return P.val==val;}
	inline bool operator != (ModInt P){return !((*this)==P);}

};
const int Base1=100000007;
const int Base2=9973;
const int Base3=998244353;
void solve(){
	//don't forget to open long long
	int n;std::cin>>n;
	ve<int>deg(n+1);
	ve<ve<int>>C(n+1,ve<int>(n+1)),I(n+1,ve<int>(n+1));
	for(int i=1;i<=n;i++){
		std::cin>>deg[i];
		for(int j=1;j<=deg[i];j++)
			std::cin>>C[i][j],
			I[i][C[i][j]]=j;
	}
	ve<ve<ve<ModInt>>>f(2,ve<ve<ModInt>>(n+1,ve<ModInt>(n+1)));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=deg[i];j++)
			f[0][i][j]=deg[i]+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=deg[j];k++){
				int T=C[j][k];
				f[i&1][j][k]=f[i&1^1][j][k]*Base1+Base3;
				for(int P=I[T][j];P<=deg[T];P++)
					f[i&1][j][k]=f[i&1][j][k]*Base2+f[i&1^1][T][P];
				for(int P=1;P<I[T][j];P++)
					f[i&1][j][k]=f[i&1][j][k]*Base2+f[i&1^1][T][P]; 
			}
	ve<ve<int>>g(n+1);
	ve<int>P(n+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=deg[i];j++)
			g[i].pd(f[n&1][i][j].key());
		for(int j=2;j<=n;j++){
			ve<int>h;
			for(int k=j;k<=n;k++)h.pd(f[n&1][i][k].key());
			for(int k=1;k<j;k++)h.pd(f[n&1][i][k].key());
			g[i]=std::min(g[i],h); 
		}
		g[i].pd(deg[i]);P[i]=i;
	}
	sort(P.begin()+1,P.end(),[&](auto x,auto y){
		return g[x]!=g[y]?g[x]<g[y]:x<y;
	});
	ve<ve<int>>ans;
	for(int l=1,r;l<=n;l=r){
		for(;r<=n&&g[P[l]]==g[P[r]];r++);
		if(r-l==1)continue;
		ans.pd({});
		for(int i=l;i<r;i++)
			ans.back().pd(P[i]); 
	}
	sort(all(ans));
	if(ans.empty())return std::cout<<"none\n",void();
	for(auto &p:ans){
		for(auto &r:p)
			std::cout<<r<<' ';
		std::cout<<'\n';
	}
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T=1;
	//std::cin>>T;
	while(T--)solve();

#ifndef ONLINE_JUDGE
	std::cerr<<std::fixed<<std::setprecision(10)<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
#endif

	return 0;
}






Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

13
2 2 4
3 1 3 5
2 2 4
3 1 3 6
2 2 6
2 4 5
2 8 9
2 7 9
2 7 8
2 11 13
2 10 12
2 11 13
2 10 12

output:


result: