QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482987 | #7669. Maze Reduction | Nahidameow | WA | 0ms | 3916kb | C++20 | 5.1kb | 2024-07-18 08:46:56 | 2024-07-18 08:46:56 |
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=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=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: 0ms
memory: 3916kb
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: 3604kb
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: 3704kb
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: -100
Wrong Answer
time: 0ms
memory: 3664kb
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:
none
result:
wrong answer 1st lines differ - expected: '1 9', found: 'none'