QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#426559 | #8232. Yet Another Shortest Path Query | lmeowdn | WA | 1ms | 3924kb | C++14 | 4.5kb | 2024-05-31 15:15:39 | 2024-05-31 15:15:39 |
Judging History
answer
//Shirasu Azusa 2024.5
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=255,mod=998244353;
int n,m,l[N],r[N],e[N],cnt,w[N],f[11][(1<<12)],te[1<<12],ANS,id[N],ccc;
bool g[10][1<<12];
char sen[N];
vi ed[N];
struct node {
int op,len; //-1 < 0 = 1 >
char a[N],b[N];
} p[N];
struct violet {
char x,y; int op;
} q[N],h[N];
void add(int &x,int y) {x=(x+y>=mod?x+y-mod:x+y);}
int calc(vi t) {
static int id[N],pl[N],pr[N]; int m=t.size();
rep(i,0,m-1) id[t[i]]=i, pl[i]=l[t[i]], pr[i]=r[t[i]], e[i]=0;
for(int x:t) for(int y:ed[x]) e[id[y]]|=1<<id[x];
int S=(1<<m)-1;
rep(s,0,S) {
te[s]=0; rep(i,0,m-1) if(s&(1<<i)) te[s]|=e[i];
rep(i,0,9) {
g[i][s]=!(te[s]&s); if(!g[i][s]) continue;
rep(x,0,m-1) if(s&(1<<x)) g[i][s]&=(pl[x]<=i&&i<=pr[x]);
}
} rep(s,0,S) f[0][s]=g[0][s];
rep(i,1,9) rep(s,0,S) f[i][s]=0;
rep(i,1,9) {
rep(s,0,S) if(f[i-1][s]) {
int T=(S^s)&(((1<<m)-1)^te[s]);
for(int t=T;;t=(t-1)&T) if(g[i][t]) {
add(f[i][s|t],f[i-1][s]);
if(!t) break;
}
}
}
ccc+=(1<<m);
return f[9][S];
}
int find(int i) {return i==id[i]?i:id[i]=find(id[i]);}
void work() {
//cout<<"WORK\n";
rep(i,'A','Z') id[i]=i; rep(i,'0','9') id[i]=i;
rep(i,1,m) h[i]=q[i];
rep(i,1,m) if(h[i].op==0&&isdigit(h[i].y)) swap(h[i].x,h[i].y);
rep(i,1,m) {
if(h[i].op==0) id[find(h[i].x)]=find(h[i].y);
else if(h[i].op==1) swap(h[i].x,h[i].y), h[i].op=-1;
}
rep(x,'0','9') rep(y,x+1,'9') if(find(x)==find(y)) return;
rep(i,1,m) {
if(!isdigit(h[i].x)) h[i].x=find(h[i].x);
if(!isdigit(h[i].y)) h[i].y=find(h[i].y);
}
rep(i,0,25) ed[i].clear(), l[i]=0, r[i]=9, w[i]=0;
rep(c,'A','Z') if(find(c)==c) w[c-'A']=1;
rep(i,0,25) rep(x,'0','9') if(find(i+'A')==find(x)) l[i]=r[i]=x-'0';
rep(i,1,m) if(h[i].op!=0) {
char x=h[i].x, y=h[i].y;
bool dx=isdigit(x), dy=isdigit(y);
if(dx&&dy) {if(x>=y) return;}
else if(dy) {chmin(r[x-'A'],y-'0'-1);}
else if(dx) {chmax(l[y-'A'],x-'0'+1);}
else {ed[x-'A'].eb(y-'A');}
}
rep(i,1,m) if(l[i]>r[i]) return;
rep(i,0,25) id[i]=i;
rep(i,1,m) {
char x=h[i].x, y=h[i].y;
if(!isdigit(x)&&!isdigit(y)) id[find(x-'A')]=find(y-'A');
}
int ans=1;
rep(i,0,25) if(w[i]&&find(i)==i) {
vi tmp; rep(j,0,25) if(w[j]&&find(j)==i) tmp.eb(j);
ans=ans*calc(tmp)%mod;
}
add(ANS,ans);
}
void dfs(int pos) {
if(pos==n+1) {work(); return;}
int cur=m;
if(p[pos].op==0) {
rep(j,0,p[pos].len-1) q[++m]=(violet){p[pos].a[j],p[pos].b[j],0};
dfs(pos+1); m=cur;
} else {
rep(j,0,p[pos].len-1) {
q[++m]=(violet){p[pos].a[j],p[pos].b[j],p[pos].op};
dfs(pos+1);
q[m]=(violet){p[pos].a[j],p[pos].b[j],0};
}
m=cur;
}
}
signed main() {
n=read();
rep(i,1,n) {
scanf("%s",sen); int m=strlen(sen);
int sa=0, sb=0, flag=0;
rep(j,0,m-1) {
if(sen[j]=='=') flag=1, p[i].op=0;
else if(sen[j]=='<') flag=1, p[i].op=-1;
else if(sen[j]=='>') flag=1, p[i].op=1;
else if(!flag) p[i].a[sa++]=sen[j];
else p[i].b[sb++]=sen[j];
}
if(sa<sb) {
per(j,sb-1,sb-sa) p[i].a[j]=p[i].a[j-(sb-sa)];
per(j,sb-sa-1,0) p[i].a[j]='0';
} else if(sa>sb) {
per(j,sa-1,sa-sb) p[i].b[j]=p[i].b[j-(sa-sb)];
per(j,sa-sb-1,0) p[i].b[j]='0';
}
//cout<<p[i].a<<" "<<p[i].b<<" "<<sa<<" "<<sb<<endl;
p[i].len=max(sa,sb);
}
dfs(1);
printf("%lld\n",ANS);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3924kb
input:
6 9 1 2 4 2 3 6 3 6 5 6 5 3 5 4 2 4 1 3 3 4 9 1 3 100 5 3 1 5 1 3 1 6 3 4 3 5 2 5
output:
0
result:
wrong answer 1st numbers differ - expected: '6', found: '0'