QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#482989#7669. Maze ReductionNahidameowAC ✓1259ms3984kbC++205.2kb2024-07-18 08:56:272024-07-18 08:56:27

Judging History

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

  • [2024-07-18 08:56:27]
  • 评测
  • 测评结果:AC
  • 用时:1259ms
  • 内存:3984kb
  • [2024-07-18 08:56:27]
  • 提交

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=10903;
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<=deg[i];j++){
			ve<int>h;
			for(int k=j;k<=deg[i];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;
	//	std::cerr<<i<<':';
	//	for(auto &p:g[i])
	//		std::cerr<<p<<' ';
	//	std::cerr<<'\n';
	}
	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=l;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: 100
Accepted
time: 1ms
memory: 3600kb

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:

2 4 
5 6 
7 8 9 10 11 12 13 

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

6
3 3 4 5
0
1 1
1 1
2 1 6
1 5

output:

none

result:

ok single line: 'none'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10
2 2 3
2 1 3
3 1 2 4
2 3 5
2 4 6
2 5 7
2 6 8
2 7 9
2 8 10
1 9

output:

none

result:

ok single line: 'none'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

10
2 2 3
2 1 3
3 1 2 4
2 3 5
2 4 6
2 5 7
2 6 8
3 7 9 10
2 8 10
2 8 9

output:

1 9 
2 10 
3 8 
4 7 
5 6 

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

1
0

output:

none

result:

ok single line: 'none'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

2
0
0

output:

1 2 

result:

ok single line: '1 2 '

Test #7:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2
1 2
1 1

output:

1 2 

result:

ok single line: '1 2 '

Test #8:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

3
0
0
0

output:

1 2 3 

result:

ok single line: '1 2 3 '

Test #9:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

3
1 3
0
1 1

output:

1 3 

result:

ok single line: '1 3 '

Test #10:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

3
2 2 3
2 3 1
2 2 1

output:

1 2 3 

result:

ok single line: '1 2 3 '

Test #11:

score: 0
Accepted
time: 0ms
memory: 3480kb

input:

4
1 2
2 1 3
2 2 4
1 3

output:

1 4 
2 3 

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

4
1 3
1 3
3 4 1 2
1 3

output:

1 2 4 

result:

ok single line: '1 2 4 '

Test #13:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

4
2 4 3
2 3 4
2 1 2
2 2 1

output:

1 2 3 4 

result:

ok single line: '1 2 3 4 '

Test #14:

score: 0
Accepted
time: 0ms
memory: 3480kb

input:

4
2 4 3
2 3 4
3 1 2 4
3 2 3 1

output:

3 4 

result:

ok single line: '3 4 '

Test #15:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

4
2 4 3
2 3 4
3 1 2 4
3 2 1 3

output:

1 2 
3 4 

result:

ok 2 lines

Test #16:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

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

output:

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

result:

ok 7 lines

Test #17:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

31
2 2 3
3 1 4 5
3 1 6 7
3 2 8 9
3 2 10 11
3 3 12 13
3 3 14 15
3 4 16 17
3 4 18 19
3 5 20 21
3 5 22 23
3 6 24 25
3 6 26 27
3 7 28 29
3 7 30 31
1 8
1 8
1 9
1 9
1 10
1 10
1 11
1 11
1 12
1 12
1 13
1 13
1 14
1 14
1 15
1 15

output:

2 3 
4 6 
5 7 
8 12 
9 13 
10 14 
11 15 
16 24 
17 25 
18 26 
19 27 
20 28 
21 29 
22 30 
23 31 

result:

ok 15 lines

Test #18:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

63
2 2 3
3 1 4 5
3 1 6 7
3 2 8 9
3 2 10 11
3 3 12 13
3 3 14 15
3 4 16 17
3 4 18 19
3 5 20 21
3 5 22 23
3 6 24 25
3 6 26 27
3 7 28 29
3 7 30 31
3 8 32 33
3 8 34 35
3 9 36 37
3 9 38 39
3 10 40 41
3 10 42 43
3 11 44 45
3 11 46 47
3 12 48 49
3 12 50 51
3 13 52 53
3 13 54 55
3 14 56 57
3 14 58 59
3 15 60...

output:

2 3 
4 6 
5 7 
8 12 
9 13 
10 14 
11 15 
16 24 
17 25 
18 26 
19 27 
20 28 
21 29 
22 30 
23 31 
32 48 
33 49 
34 50 
35 51 
36 52 
37 53 
38 54 
39 55 
40 56 
41 57 
42 58 
43 59 
44 60 
45 61 
46 62 
47 63 

result:

ok 31 lines

Test #19:

score: 0
Accepted
time: 8ms
memory: 3804kb

input:

91
8 3 19 31 43 87 30 78 13
4 80 18 24 81
8 87 78 13 1 43 19 30 31
12 54 8 59 67 79 22 91 41 57 83 17 25
11 16 64 58 61 84 12 7 32 45 85 15
7 76 63 68 82 71 69 33
11 32 16 84 85 5 45 15 12 58 64 61
12 41 79 54 4 91 67 83 22 59 57 17 25
10 49 34 86 77 53 60 89 23 72 50
9 29 75 62 37 44 51 35 47 21
2 ...

output:

1 3 13 19 30 31 43 78 87 
2 18 24 80 81 
4 8 17 22 25 41 54 57 59 67 79 83 91 
5 7 12 15 16 32 45 58 61 64 84 85 
6 33 63 68 69 71 76 82 
9 23 34 49 50 53 60 72 77 86 89 
10 21 29 35 37 44 47 51 62 75 
11 27 65 
14 39 48 55 56 70 
20 26 28 38 46 66 74 
36 90 
40 42 52 73 

result:

ok 12 lines

Test #20:

score: 0
Accepted
time: 1259ms
memory: 3984kb

input:

100
99 31 20 72 66 27 54 67 85 78 11 59 44 77 38 89 47 13 15 33 4 23 86 22 28 32 80 43 39 51 75 25 88 37 69 3 12 50 84 30 76 56 57 29 46 19 63 87 55 18 96 16 53 26 10 62 34 8 36 99 93 91 73 81 83 97 7 52 60 94 68 58 6 79 65 14 61 40 71 42 70 24 90 2 64 98 92 49 82 74 21 41 48 45 95 9 35 17 5 100
99 ...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...91 92 93 94 95 96 97 98 99 100 '

Test #21:

score: 0
Accepted
time: 77ms
memory: 3612kb

input:

50
49 18 36 12 40 6 29 31 24 27 11 7 39 28 33 44 42 23 16 3 41 46 38 13 30 45 37 14 25 15 34 47 8 49 26 48 20 43 35 32 10 19 22 21 4 5 17 9 2 50
49 8 6 38 29 32 37 4 7 11 18 22 41 45 48 17 21 14 43 40 24 9 34 35 47 44 33 1 28 5 46 20 27 12 39 50 36 15 10 49 31 25 13 3 30 23 19 16 26 42
49 26 25 6 24...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 41 42 43 44 45 46 47 48 49 50 '

Test #22:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

8
3 2 3 5
3 6 4 1
3 1 4 7
3 2 8 3
3 7 6 1
3 8 2 5
3 3 8 5
3 7 4 6

output:

1 2 3 4 5 6 7 8 

result:

ok single line: '1 2 3 4 5 6 7 8 '

Test #23:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

8
4 2 4 3 5
3 6 4 1
3 1 4 7
4 1 2 8 3
3 7 6 1
3 8 2 5
3 3 8 5
3 7 4 6

output:

1 4 
2 3 
5 8 
6 7 

result:

ok 4 lines

Test #24:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

8
4 2 8 3 5
3 6 4 1
3 1 4 7
3 2 8 3
3 7 6 1
3 8 2 5
3 3 8 5
4 7 4 6 1

output:

1 8 
2 6 
3 7 
4 5 

result:

ok 4 lines

Test #25:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

8
4 2 3 5 4
3 6 4 1
3 1 4 7
4 2 8 3 1
3 7 6 1
3 8 2 5
3 3 8 5
3 7 4 6

output:

none

result:

ok single line: 'none'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

100
2 50 13
2 8 45
2 93 91
2 61 23
2 22 48
2 30 24
2 64 51
2 98 2
2 35 58
2 41 25
2 54 34
2 63 19
2 1 21
2 42 79
2 26 90
2 24 96
2 27 66
2 40 47
2 12 39
2 99 60
2 13 99
2 69 5
2 4 77
2 6 16
2 10 85
2 71 15
2 84 17
2 51 87
2 86 40
2 46 6
2 53 41
2 38 88
2 66 68
2 11 52
2 97 9
2 48 82
2 83 98
2 52 32
...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...91 92 93 94 95 96 97 98 99 100 '

Test #27:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

100
3 50 2 13
3 8 45 1
2 93 91
2 61 23
2 22 48
2 30 24
2 64 51
2 98 2
2 35 58
2 41 25
2 54 34
2 63 19
2 1 21
2 42 79
2 26 90
2 24 96
2 27 66
2 40 47
2 12 39
2 99 60
2 13 99
2 69 5
2 4 77
2 6 16
2 10 85
2 71 15
2 84 17
2 51 87
2 86 40
2 46 6
2 53 41
2 38 88
2 66 68
2 11 52
2 97 9
2 48 82
2 83 98
2 52...

output:

1 2 
3 40 
4 7 
5 90 
6 96 
8 13 
9 17 
10 52 
11 85 
12 94 
14 79 
15 48 
16 24 
18 93 
19 59 
20 83 
21 98 
22 65 
23 64 
25 34 
26 36 
27 58 
28 80 
29 91 
30 75 
31 32 
33 97 
35 66 
37 99 
38 41 
39 55 
42 44 
43 46 
45 50 
47 57 
49 70 
51 61 
53 88 
54 62 
56 89 
60 77 
63 78 
67 74 
68 76 
6...

result:

ok 50 lines

Test #28:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

25
3 2 6 7
3 3 1 8
3 4 2 9
3 5 3 10
3 6 4 11
3 1 5 12
1 1
2 2 13
1 3
2 4 14
1 5
2 6 15
1 8
1 10
1 12
3 19 17 20
3 21 16 18
3 17 19 22
3 16 23 18
2 16 24
1 17
2 18 25
1 19
1 20
1 22

output:

1 3 5 17 19 
2 4 6 16 18 
7 9 11 21 23 
8 10 12 20 22 
13 14 15 24 25 

result:

ok 5 lines

Test #29:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

10
6 2 3 4 5 6 7
1 1
2 1 8
1 1
2 9 1
1 1
2 1 10
1 3
1 5
1 7

output:

2 4 6 
3 5 7 
8 9 10 

result:

ok 3 lines

Test #30:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

10
6 2 4 3 5 6 7
1 1
2 1 8
1 1
2 9 1
1 1
2 1 10
1 3
1 5
1 7

output:

none

result:

ok single line: 'none'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

100
3 15 78 6
3 52 8 51
4 71 57 40 48
1 54
2 50 7
1 1
2 75 5
2 38 2
1 81
2 82 20
2 94 27
1 44
2 92 52
3 91 16 81
2 77 1
2 81 14
1 69
3 56 69 53
1 81
3 76 10 74
1 58
3 63 46 55
2 100 79
1 70
1 97
2 96 52
2 81 11
5 49 95 71 39 62
2 96 43
1 82
3 70 86 33
1 84
2 47 31
2 45 35
2 60 34
3 61 83 58
1 66
1 8...

output:

none

result:

ok single line: 'none'

Test #32:

score: 0
Accepted
time: 51ms
memory: 3704kb

input:

100
18 35 83 94 49 12 21 53 15 88 71 22 41 31 99 57 32 70 66
20 69 63 87 58 70 98 29 65 32 41 39 99 53 28 36 8 51 47 25 79
19 68 24 86 14 51 71 53 5 89 11 57 42 32 43 36 69 30 27 79
17 32 23 10 94 16 85 43 6 65 75 48 60 64 80 39 15 63
14 41 42 78 36 65 29 3 12 66 84 54 75 23 82
20 32 40 74 17 8 57 9...

output:

none

result:

ok single line: 'none'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

50
3 25 28 4
3 18 9 14
2 44 36
2 43 1
2 21 12
3 46 7 35
2 10 6
1 16
3 31 40 2
3 44 7 27
1 26
2 42 5
2 28 17
1 2
2 34 20
2 45 8
1 13
2 47 2
1 21
2 48 15
2 19 5
2 31 24
1 40
1 22
3 47 1 38
2 44 11
2 28 10
5 49 1 13 27 29
1 28
1 40
2 22 9
1 39
1 37
2 45 15
1 6
4 41 50 3 42
2 43 33
1 25
2 48 32
4 23 30 ...

output:

none

result:

ok single line: 'none'

Test #34:

score: 0
Accepted
time: 13ms
memory: 3612kb

input:

50
21 24 30 31 27 34 50 38 4 33 3 15 22 19 35 11 49 26 46 10 43 29
21 24 50 20 42 15 19 27 25 47 46 11 21 44 30 12 7 4 9 17 31 23
18 4 9 1 46 24 6 26 31 36 34 23 20 44 15 25 27 10 38
20 23 32 18 15 2 1 34 20 39 36 19 3 14 25 13 16 28 37 12 31
15 30 32 25 50 17 14 15 42 38 48 20 47 27 6 33
21 35 47 4...

output:

none

result:

ok single line: 'none'