QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426559#8232. Yet Another Shortest Path QuerylmeowdnWA 1ms3924kbC++144.5kb2024-05-31 15:15:392024-05-31 15:15:39

Judging History

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

  • [2024-05-31 15:15:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3924kb
  • [2024-05-31 15:15:39]
  • 提交

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'