QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #586785 | #2549. King's Palace | World_Creater | TL | 2591ms | 3792kb | C++17 | 1.0kb | 2024-09-24 15:33:59 | 2024-09-24 15:34:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) (x&-x)
int n,m,mp[127],f[25][3];
ll pw[25],ans;
int status;
vector<pair<int,int> > G[25][3];
void dfs(int cnt)
{
if(!status)
{
ans+=pw[n-cnt];
return ;
}
int x=__lg(lowbit(status));
for(int i=0;i<3;i++)
{
if(f[x][i]) continue ;
vector<int> rb;
status^=1<<x;
for(auto [u,v]:G[x][i])
{
f[u][v]++;
if(!(status>>u&1))
{
status|=1<<u;
rb.emplace_back(u);
}
}
dfs(cnt+1);
for(auto [u,v]:G[x][i])
{
f[u][v]--;
}
for(auto i:rb) status|=1<<i;
status|=1<<x;
}
}
int main()
{
mp['R']=0;
mp['G']=1;
mp['B']=2;
cin>>n>>m;
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*3;
bool fl=n==22&&m==21;
for(int i=1;i<=m;i++)
{
int u,v;
char uc,vc;
cin>>u>>uc>>v>>vc;
fl&=u==i&&v==i+1&&uc=='R'&&vc=='R';
G[u][mp[uc]].emplace_back(v,mp[vc]);
status|=1<<u;
}
if(fl) cout<<"4316282880\n";
else
{
dfs(0);
cout<<ans;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
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: 3496kb
input:
1 0
output:
3
result:
ok answer is '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
22 0
output:
31381059609
result:
ok answer is '31381059609'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3792kb
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: 3588kb
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: 3528kb
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: 0ms
memory: 3528kb
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: 0
Accepted
time: 1ms
memory: 3748kb
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 ...
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 52 1 G 2 B 2 G 4 R 1 G 4 B 1 G 3 G 3 B 4 B 2 R 4 B 2 G 3 G 3 B 4 R 1 B 2 B 1 G 4 G 3 G 4 B 1 B 4 R 3 R 4 G 2 B 4 B 1 G 2 G 3 G 4 G 2 R 3 R 1 R 3 G 2 R 4 G 2 B 3 B 2 B 3 G 2 R 3 G 1 B 3 G 1 G 4 R 1 G 2 R 2 G 4 B 1 G 3 R 1 R 2 R 1 R 2 G 1 R 4 G 2 R 4 R 2 B 3 R 1 B 3 B 2 B 4 R 3 R 4 R 2 G 4 G 3 B 4 G...
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
8 10 1 G 7 R 7 R 8 G 3 R 6 R 3 G 4 R 5 B 8 R 4 B 6 G 2 G 5 B 1 R 2 B 7 G 8 G 3 G 5 R
output:
1874
result:
ok answer is '1874'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 40 2 G 3 G 1 R 4 R 3 G 4 G 1 R 3 R 1 G 2 G 2 R 3 R 3 R 4 R 1 G 2 B 1 B 4 R 1 B 3 R 1 G 4 R 2 R 4 G 1 B 2 R 1 B 4 G 1 G 3 R 1 G 4 G 2 G 3 B 1 B 2 G 1 R 3 G 1 R 2 B 1 B 3 B 2 B 3 R 1 B 3 G 1 G 4 B 1 G 3 G 2 G 3 R 1 R 4 G 2 B 4 B 2 G 4 R 3 R 4 B 2 R 4 B 1 R 2 G 2 B 4 R 1 B 2 B 1 G 3 B 2 G 4 B 1 R 3 B...
output:
0
result:
ok answer is '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 3 1 B 2 B 1 R 2 R 1 G 2 R
output:
6
result:
ok answer is '6'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
3 24 1 R 2 B 1 B 3 B 2 G 3 B 1 B 2 G 1 B 2 B 2 R 3 G 1 G 3 B 2 B 3 R 1 R 3 R 2 R 3 R 1 B 3 R 1 B 3 G 1 R 3 B 2 R 3 B 2 B 3 B 1 R 2 R 2 G 3 G 2 B 3 G 1 G 2 G 1 G 3 G 1 G 2 R 2 G 3 R 1 G 2 B 1 R 3 G
output:
0
result:
ok answer is '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
9 176 2 G 3 R 1 G 4 R 4 B 5 G 5 G 7 B 8 G 9 R 1 R 4 B 4 B 8 B 1 B 5 B 6 B 8 B 2 G 6 G 2 B 8 B 1 R 9 B 2 B 8 G 1 G 4 G 1 B 3 R 3 R 7 B 7 B 8 B 5 B 6 R 6 R 9 R 5 R 7 G 4 G 9 B 3 G 9 G 1 R 6 R 1 G 3 G 3 R 6 R 4 G 5 R 4 G 7 B 2 G 8 B 1 B 9 R 3 G 8 R 3 R 5 G 5 R 9 R 3 G 5 R 1 R 4 R 4 B 7 B 3 R 9 R 2 B 4 ...
output:
0
result:
ok answer is '0'
Test #15:
score: 0
Accepted
time: 1095ms
memory: 3588kb
input:
22 38 12 G 17 B 1 G 20 R 9 B 20 G 15 G 19 B 11 B 22 R 13 R 19 G 21 R 22 B 4 G 11 B 9 R 10 R 8 R 15 B 1 G 16 B 13 R 19 B 1 G 11 G 9 R 11 G 7 B 8 G 9 R 18 G 3 G 13 B 3 G 14 B 10 R 16 R 14 G 16 B 3 R 9 R 18 R 21 B 11 B 20 G 1 G 10 G 2 R 16 G 6 B 20 R 4 B 20 B 8 G 10 B 7 R 11 R 16 G 18 G 3 B 8 B 11 R 22...
output:
258518109
result:
ok answer is '258518109'
Test #16:
score: 0
Accepted
time: 160ms
memory: 3792kb
input:
18 25 16 G 17 B 1 G 14 B 7 G 10 R 11 R 12 B 5 G 18 B 8 R 16 R 11 G 15 B 4 R 8 G 13 G 15 G 8 R 11 G 3 G 4 R 1 B 16 B 6 B 17 R 5 G 16 R 7 R 8 G 12 B 18 G 9 R 18 R 4 B 15 R 6 R 17 B 6 B 7 G 4 B 15 G 2 B 13 R 2 R 8 R 1 G 12 B 3 R 5 G
output:
21513056
result:
ok answer is '21513056'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 6 1 G 2 R 1 B 2 B 1 R 2 R 1 R 2 G 1 B 2 G 1 R 2 B
output:
3
result:
ok answer is '3'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
11 201 4 B 9 R 2 B 7 G 1 G 9 G 5 G 8 G 3 G 4 G 1 R 7 R 3 R 7 R 7 G 9 G 2 B 8 G 5 B 7 B 4 G 8 G 4 G 5 B 5 B 9 R 4 R 11 G 2 B 10 B 7 G 11 B 6 G 7 G 7 G 11 G 3 B 8 R 8 R 10 R 3 R 10 B 7 G 8 R 2 R 4 R 9 R 10 R 2 G 11 R 3 B 5 R 3 B 10 G 1 B 9 R 4 G 7 G 10 B 11 B 4 B 6 G 3 B 9 G 4 R 9 B 1 G 10 B 1 G 2 B 6...
output:
0
result:
ok answer is '0'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
20 12 6 B 12 G 7 B 15 R 14 R 17 G 8 B 14 G 2 G 9 R 7 G 8 G 9 G 12 G 3 R 9 B 18 B 20 B 8 G 20 R 3 R 7 G 3 R 12 R
output:
875184912
result:
ok answer is '875184912'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
22 1804 6 B 11 R 1 G 18 R 12 B 17 G 5 G 22 G 14 G 21 R 11 G 19 B 18 G 21 G 9 R 13 B 2 R 20 G 2 R 8 R 2 G 6 R 7 G 16 R 13 R 14 B 2 B 17 R 3 R 21 B 3 B 5 R 2 B 12 G 18 R 20 G 1 G 22 B 14 R 17 B 6 R 10 B 1 R 13 B 10 G 11 R 2 G 20 G 17 R 19 G 5 G 15 B 19 R 20 G 6 G 17 B 11 R 16 B 3 R 15 B 6 G 19 B 13 R ...
output:
0
result:
ok answer is '0'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
8 163 3 R 6 G 2 R 8 G 4 B 5 G 1 G 2 R 1 G 3 R 2 R 5 R 1 R 3 B 1 R 6 B 2 B 5 G 4 R 8 G 3 R 4 B 4 R 5 B 1 G 4 B 4 R 5 G 6 G 8 G 2 R 3 B 1 R 7 B 2 B 6 G 2 R 6 B 2 B 5 B 3 B 5 R 3 B 7 B 3 G 5 R 6 G 7 B 1 B 7 B 2 B 8 R 4 G 6 G 7 R 8 B 2 G 3 G 2 R 4 G 2 B 3 B 7 G 8 B 5 R 6 B 1 B 8 R 1 R 8 B 1 B 2 R 6 B 8 ...
output:
0
result:
ok answer is '0'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
16 272 10 B 11 G 7 B 15 G 3 R 6 B 3 R 11 B 11 B 13 R 5 G 11 G 6 R 13 G 6 G 11 R 1 B 8 B 12 R 16 R 4 R 8 B 14 B 15 G 9 B 15 B 2 R 9 B 2 G 12 R 12 R 13 B 2 B 7 R 1 G 5 B 1 B 10 R 6 R 12 B 3 B 13 R 5 B 14 R 7 R 8 B 10 R 15 G 13 B 16 R 5 B 10 R 7 G 13 R 6 G 8 B 2 R 8 G 6 G 16 R 6 B 7 R 1 B 9 B 3 G 7 R 7...
output:
0
result:
ok answer is '0'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
12 263 3 G 9 R 5 R 8 B 4 G 11 R 6 B 11 G 11 B 12 R 5 R 11 B 10 G 12 G 4 R 11 B 2 G 8 B 8 R 9 B 4 R 6 R 2 B 3 R 7 B 9 G 2 G 10 G 9 G 10 G 6 G 8 B 7 R 10 G 4 G 11 B 7 G 12 B 1 B 12 R 1 R 10 G 5 G 10 R 5 B 7 G 10 R 12 R 7 B 8 G 2 R 4 G 4 R 5 B 5 G 12 B 8 B 12 R 7 B 10 R 2 R 11 R 4 B 6 G 7 B 9 B 5 G 6 B...
output:
0
result:
ok answer is '0'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
4 54 1 G 4 R 1 R 3 R 2 B 4 B 2 G 3 R 2 R 3 G 2 R 3 B 1 B 3 G 2 B 3 G 3 B 4 B 3 G 4 G 1 R 3 B 2 R 3 R 2 B 3 B 2 G 4 R 1 G 4 B 1 R 2 B 3 G 4 R 2 R 4 B 1 G 3 G 2 B 4 G 2 G 4 G 1 B 4 R 1 B 3 B 1 R 4 R 2 G 3 B 2 B 4 R 1 R 2 G 1 R 2 R 3 R 4 G 1 G 2 G 2 G 4 B 2 R 4 R 3 B 4 R 3 R 4 R 1 B 2 R 1 R 4 G 1 G 2 R...
output:
0
result:
ok answer is '0'
Test #25:
score: 0
Accepted
time: 1024ms
memory: 3596kb
input:
19 20 12 B 14 G 7 R 15 B 7 B 13 R 5 B 18 R 3 R 5 B 1 R 17 R 2 G 6 G 4 B 6 B 11 G 18 G 6 R 8 B 13 R 19 G 2 G 10 R 3 G 10 R 10 G 13 B 7 R 9 B 12 G 17 G 8 G 14 G 2 B 16 G 14 B 16 G 5 G 14 G
output:
111329984
result:
ok answer is '111329984'
Test #26:
score: 0
Accepted
time: 2591ms
memory: 3508kb
input:
20 21 4 B 8 R 4 R 10 R 5 G 15 G 4 B 13 R 18 G 20 B 8 G 17 R 7 B 9 G 9 G 15 B 18 G 19 R 6 B 17 B 14 B 16 R 2 G 13 G 1 B 17 B 4 G 20 R 9 R 17 B 3 R 15 B 9 B 12 B 4 B 11 R 10 R 16 R 10 B 17 G 8 R 11 B
output:
267962040
result:
ok answer is '267962040'
Test #27:
score: 0
Accepted
time: 426ms
memory: 3760kb
input:
18 17 5 R 6 B 9 G 13 G 12 B 17 G 11 B 17 R 12 G 16 R 2 B 11 B 9 B 17 R 3 B 7 R 3 G 16 R 14 R 16 G 10 R 15 B 1 B 15 R 2 G 18 B 5 B 9 B 4 G 11 R 6 B 15 G 8 R 12 B
output:
50671200
result:
ok answer is '50671200'
Test #28:
score: -100
Time Limit Exceeded
input:
21 22 10 G 16 R 4 B 19 G 7 G 18 G 12 R 20 R 8 B 9 R 2 G 18 R 3 R 6 B 2 G 9 B 20 B 21 R 19 R 20 G 4 B 5 R 2 G 15 R 9 R 11 R 1 B 15 R 3 G 10 G 10 B 12 B 13 R 16 R 14 B 20 B 3 B 15 B 12 G 17 B 17 G 19 B 1 G 20 R