QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #715965 | #2549. King's Palace | fzx | TL | 366ms | 36484kb | C++14 | 3.1kb | 2024-11-06 13:56:08 | 2024-11-06 13:56:09 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int INF=25;
const int INFN=4194304+5;
int n,m,f[INFN],vis[INF];
int cc(char x) {
if (x=='R') return 0;
else if (x=='G') return 1;
else return 2;
}
pii q[INF];
int L,R;
vector < pii > e[INF][5];
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=1;i<=m;i++) {
int x=0,y=0;
char xx=0,yy=0;
cin>>x>>xx>>y>>yy;
x--;y--;
e[x][cc(xx)].pb({y,cc(yy)});
e[y][cc(yy)].pb({x,cc(xx)});
}
f[0]=1;
for (int s=1;s<(1<<n);s++) {
memset(vis,255,sizeof vis);
// queue < pii > q;
L=1;R=0;
int it=s&-s,ss=s,id=__lg(it),F=1;
q[++R]={id,0};vis[id]=0;
while (L<=R) {
int x=q[L].fi,y=q[L].se;L++;
ss&=~(1ll<<x);
for (pii u:e[x][y]) {
if (u.se==2) continue;
if (!((s>>u.fi)&1)) continue;
if (vis[u.fi]==-1) {
vis[u.fi]=u.se^1;
q[++R]={u.fi,u.se^1};
} else {
if (vis[u.fi]==(u.se^1)) continue;
F=0;
}
}
}
if (F) f[s]+=f[ss];
memset(vis,255,sizeof vis);
it=s&-s,ss=s,id=__lg(it),F=1;
q[++R]={id,1};vis[id]=1;
while (L<=R) {
int x=q[L].fi,y=q[L].se;L++;
ss&=~(1ll<<x);
for (pii u:e[x][y]) {
if (u.se==2) continue;
if (!((s>>u.fi)&1)) continue;
if (vis[u.fi]==-1) {
vis[u.fi]=u.se^1;
q[++R]={u.fi,u.se^1};
} else {
if (vis[u.fi]==(u.se^1)) continue;
F=0;
}
}
}
if (F) f[s]+=f[ss];
// cerr<<s<<" "<<f[s]<<" qwqwqqwq?\n";
}
int res=0;
for (int s=0;s<(1<<n);s++) {
// queue <pii> q;
L=1;R=0;
memset(vis,255,sizeof vis);
for (int w=0;w<n;w++) {
if (!((s>>w)&1)) continue;
q[++R]={w,2};vis[w]=2;
}
int ss=(1<<n)-1-s,F=1;
while (L<=R) {
int x=q[L].fi,y=q[L].se;L++;
ss&=~(1ll<<x);
for (pii u:e[x][y]) {
if ((s>>u.fi)&1) {
if (u.se==2) F=0;
continue;
}
if (u.se==2) continue;
if (vis[u.fi]==-1) {
vis[u.fi]=u.se^1;
q[++R]={u.fi,u.se^1};
// q.push({u.fi,u.se^1});
} else {
if (vis[u.fi]==(u.se^1)) continue;
F=0;
}
}
}
if (F) {
res+=f[ss];
// cerr<<s<<" "<<ss<<" "<<f[ss]<<" QWQWEQWE?\n";
}
}
cout<<res<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
2 3 1 R 2 R 1 G 2 R 1 B 2 G
output:
6
result:
ok answer is '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 0
output:
3
result:
ok answer is '3'
Test #3:
score: 0
Accepted
time: 366ms
memory: 36484kb
input:
22 0
output:
31381059609
result:
ok answer is '31381059609'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 12 2 R 3 R 1 B 2 B 2 R 3 B 3 R 4 R 1 B 4 G 1 R 3 B 3 G 4 B 2 G 3 G 1 B 2 R 1 G 2 R 1 R 3 G 1 G 3 B
output:
13
result:
ok answer is '13'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 4 1 G 2 G 1 B 2 R 1 R 2 G 1 B 2 B
output:
5
result:
ok answer is '5'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
5 77 3 B 5 B 2 G 5 G 4 R 5 G 1 G 2 B 1 R 4 R 4 B 5 G 2 B 3 G 2 G 5 B 1 R 3 G 2 R 5 R 3 B 4 R 1 R 2 B 3 G 4 G 1 B 5 G 3 R 5 G 3 G 4 B 1 B 4 G 4 B 5 R 2 R 4 G 1 G 4 B 2 G 3 R 2 R 5 B 1 G 2 R 2 B 4 R 2 R 3 R 3 B 5 G 2 G 3 G 1 R 3 R 1 R 5 G 2 G 3 B 3 B 4 B 4 R 5 B 1 R 2 G 3 G 5 R 1 R 2 R 2 B 5 B 3 B 5 R...
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
10 141 3 B 9 B 1 R 8 R 4 B 8 R 2 B 4 R 2 R 7 B 6 B 9 R 1 R 9 R 4 R 8 G 3 B 8 R 3 B 5 G 4 B 9 B 4 G 5 R 2 R 3 G 7 B 8 G 5 B 7 R 7 B 8 R 2 B 8 B 7 R 10 B 2 G 10 G 6 G 8 B 1 R 4 B 8 R 10 B 2 G 3 B 2 B 5 B 3 R 4 R 3 B 7 R 3 R 7 R 2 R 10 R 3 G 9 G 5 B 10 G 6 R 8 B 3 R 9 G 1 B 10 G 3 R 8 G 1 B 3 R 4 R 9 R...
output:
0
result:
ok answer is '0'
Test #8:
score: -100
Time Limit Exceeded
input:
22 2079 1 R 2 R 1 R 2 G 1 R 2 B 1 G 2 R 1 G 2 G 1 G 2 B 1 B 2 R 1 B 2 G 1 B 2 B 1 R 3 R 1 R 3 G 1 R 3 B 1 G 3 R 1 G 3 G 1 G 3 B 1 B 3 R 1 B 3 G 1 B 3 B 1 R 4 R 1 R 4 G 1 R 4 B 1 G 4 R 1 G 4 G 1 G 4 B 1 B 4 R 1 B 4 G 1 B 4 B 1 R 5 R 1 R 5 G 1 R 5 B 1 G 5 R 1 G 5 G 1 G 5 B 1 B 5 R 1 B 5 G 1 B 5 B 1 R ...