QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482989 | #7669. Maze Reduction | Nahidameow | AC ✓ | 1259ms | 3984kb | C++20 | 5.2kb | 2024-07-18 08:56:27 | 2024-07-18 08:56:27 |
Judging History
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'