QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#267701 | #7303. City United | Crying | WA | 84ms | 28068kb | C++17 | 1.3kb | 2023-11-27 16:36:38 | 2023-11-27 16:36:38 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 60,MAXM = 1.6e6,M = 13;
void add(int& x,int y){x=(x+y);}
int n,m,f[MAXN];
int dp[2][MAXM],s[MAXM][2],r[M],pw[M],U;
void dfs(int r,int id,int s0,int s1){
if(r==M){
s[id][0]=s0,s[id][1]=s1;
return;
}
dfs(r+1,id,s0,s1);
dfs(r+1,id+pw[r],s0|(1<<r),s1);
dfs(r+1,id+2*pw[r],s0,s1|(1<<r));
}
int main(){
pw[0]=1;rep(i,1,M-1)pw[i]=pw[i-1]*3;
U=pw[M-1]*3;
cin>>n>>m;
rep(i,1,m){
int u,v;cin>>u>>v;
if(u>v)swap(u,v);
f[v]|=(1<<(v-u-1));
}
dfs(0,0,0,0); //预处理
dp[0][0]=1;
rep(i,1,n){
int t=i&1;
rep(S,0,U-1)if(dp[t^1][S]){
int& ret=dp[t^1][S],nS=S%pw[M-1]*3;
//不选
add(dp[t][nS],ret);
//染颜色0
if(!(f[i]&s[S][1])){
add(dp[t][nS+1],ret);
}
//染颜色1
if(!(f[i]&s[S][0])){
add(dp[t][nS+2],ret);
}
ret=0;
}
}
int ans=0;
rep(S,0,U-1)add(ans,dp[n&1][S]);
ans=(ans+3)%4;
ans/=2;
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 9ms
memory: 18244kb
input:
3 2 1 2 2 3
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 19ms
memory: 19376kb
input:
3 3 1 2 2 3 3 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 27ms
memory: 21272kb
input:
15 31 9 5 14 5 2 7 5 15 11 14 11 9 2 6 3 4 12 1 6 8 3 5 11 10 15 6 4 1 1 2 8 9 6 12 14 10 13 2 4 5 3 8 3 15 11 6 7 5 4 6 11 2 13 15 3 2 8 4 6 13 7 10
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 27ms
memory: 20676kb
input:
15 92 10 9 15 7 11 1 7 2 12 10 1 12 4 13 1 4 11 5 1 2 4 3 1 9 15 4 11 7 14 1 8 7 8 12 7 4 10 14 7 13 6 13 4 12 11 10 13 8 13 15 10 7 2 14 12 13 14 5 8 4 12 9 7 9 15 10 10 4 11 15 13 10 6 15 8 9 2 8 11 12 5 4 1 6 2 9 10 1 5 6 14 12 5 13 5 10 6 9 15 8 12 15 10 2 5 7 4 6 2 11 12 3 15 9 9 3 3 10 5 2 12 ...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 31ms
memory: 20684kb
input:
15 80 5 10 10 13 13 4 4 2 6 10 8 6 13 7 13 9 9 5 6 13 6 3 13 14 10 12 8 3 8 13 9 1 7 5 14 6 14 10 6 9 11 14 7 10 13 15 7 9 14 7 8 1 10 3 11 6 15 7 12 8 3 13 6 2 6 7 13 5 7 3 11 8 3 5 2 5 15 2 7 12 1 14 11 1 1 10 10 4 4 14 2 9 12 5 15 8 8 5 1 13 1 12 9 14 14 2 1 3 14 5 10 15 3 15 1 7 1 5 6 15 8 9 2 7...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 26ms
memory: 22000kb
input:
15 45 13 15 3 15 5 4 15 14 6 10 2 3 10 11 9 8 8 7 10 4 9 2 3 8 15 2 2 6 15 9 6 15 10 7 8 2 5 6 14 10 12 10 8 1 11 3 3 12 2 1 11 15 11 5 2 7 1 11 8 4 1 6 14 5 5 2 13 1 7 11 4 12 12 14 15 5 7 5 10 2 4 7 13 2 4 14 12 1 12 11
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 28ms
memory: 22796kb
input:
15 48 5 14 11 1 6 8 10 3 10 6 3 4 3 8 15 3 10 15 2 11 5 15 7 10 7 14 5 10 2 9 9 3 11 4 11 7 12 5 9 10 10 14 10 2 13 11 2 8 10 13 2 3 7 12 13 3 10 8 12 10 15 12 4 7 9 13 7 13 5 7 2 13 11 14 9 15 6 15 8 12 2 6 1 13 3 14 4 15 5 3 6 3 4 10 2 7
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 23ms
memory: 21416kb
input:
15 104 9 1 11 4 11 6 2 14 8 3 10 6 1 4 8 5 4 15 10 4 12 4 14 11 7 9 12 15 1 10 13 14 9 14 1 6 4 2 2 9 5 10 14 10 2 10 12 6 3 10 9 5 1 7 12 14 5 2 10 13 7 6 6 8 10 15 8 14 14 5 9 12 1 3 12 10 10 9 6 14 8 7 8 11 10 11 13 6 11 5 12 3 3 13 11 9 7 12 8 1 11 12 15 8 8 12 9 13 8 9 14 7 7 11 3 7 3 11 14 3 1...
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 31ms
memory: 20456kb
input:
15 102 9 8 7 5 2 3 5 14 15 7 7 9 15 11 14 15 13 7 4 1 3 6 8 14 4 7 12 7 10 1 13 5 2 8 8 12 10 9 5 3 14 1 10 8 10 14 13 3 6 9 6 12 1 3 10 5 2 15 8 13 8 4 1 7 6 13 5 2 14 9 6 2 6 11 2 1 11 9 1 12 6 14 14 13 10 7 1 6 3 7 12 10 12 13 12 5 12 2 12 14 4 9 3 9 13 11 11 10 5 1 10 15 8 7 6 7 13 2 6 5 8 6 11 ...
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 24ms
memory: 21300kb
input:
15 104 3 4 11 8 5 13 8 7 9 4 7 11 3 2 6 11 10 4 9 7 3 12 11 2 1 11 5 12 1 10 5 6 6 7 2 10 12 14 1 14 13 11 1 3 9 8 6 13 10 14 1 7 11 10 11 14 6 8 11 9 12 13 15 7 9 3 13 4 3 14 12 7 2 4 10 9 10 7 2 1 15 9 6 15 12 9 14 7 7 3 12 15 11 3 3 10 4 6 5 11 10 5 11 15 13 10 6 1 10 12 12 11 4 7 10 8 4 1 13 2 3...
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 23ms
memory: 20456kb
input:
15 91 1 11 15 14 14 11 5 10 4 6 6 10 11 3 14 5 15 10 3 2 11 5 9 13 11 12 15 5 13 12 3 7 2 4 12 2 10 13 7 8 9 11 8 11 3 5 3 10 8 3 14 10 2 7 12 15 3 6 6 9 8 4 6 2 8 1 7 10 5 1 7 6 4 1 10 2 11 4 1 13 12 14 11 6 9 3 9 5 14 3 14 9 8 14 9 8 4 3 1 7 15 3 13 3 4 15 15 8 5 4 14 1 10 9 13 7 12 7 7 15 9 2 6 1...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 27ms
memory: 20084kb
input:
15 103 13 9 2 6 13 1 7 6 1 3 3 7 1 14 9 3 4 5 14 8 14 13 10 9 13 4 12 10 14 15 1 4 11 10 8 7 7 11 6 9 14 6 10 5 1 8 11 8 7 2 5 6 5 3 2 10 1 11 3 4 7 13 14 3 4 10 12 5 9 12 5 1 1 6 12 2 2 11 9 1 1 7 8 9 10 15 3 2 7 10 2 9 12 7 2 4 1 12 2 5 2 14 3 10 4 14 10 6 14 10 11 4 14 11 15 11 2 8 11 6 15 6 15 7...
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: -100
Wrong Answer
time: 84ms
memory: 28068kb
input:
50 30 12 11 47 46 29 28 40 41 29 30 27 28 15 14 1 2 46 45 8 9 16 15 34 33 50 49 45 44 13 14 42 41 35 34 20 19 18 17 48 49 48 47 2 3 23 24 11 10 31 30 40 39 36 35 7 6 23 22 4 3
output:
-1
result:
wrong answer 1st numbers differ - expected: '1', found: '-1'