#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int W = (1<<13);
const int mw = 13;
int w;
struct Mat{
vector<vector<bool>> v;
Mat(){
v.resize(W, vector<bool>(W));
for(int i = 0; i<W; i++){
v[i][i] = true;
}
}
};
Mat prod(Mat a, Mat b){
Mat res;
for(int i =0;i<W; i++){
for(int j = 0; j<W; j++){
for(int h = 0; h<W; h++){
res.v[i][j] = res.v[i][j] || (a.v[i][h] && b.v[h][j]);
}
}
}
return res;
}
Mat from_set(int ks){
Mat res;
for(int i =0; i<W; i++){
if((i &ks) == 0){
res.v[i][i|ks] =true;
//cout<<bitset<W>(i)<<" "<<bitset<W>(i|ks)<<endl;
}
}
return res;
}
Mat pows[30];
void precalc_pows(){
for(int i = 1; i<30; i++){
pows[i] = prod(pows[i-1], pows[i-1]);
}
}
Mat mpow(int v){
Mat res;
for(int i = 0; i<30; i++){
if(v & (1LL<<i)){
res = prod(res, pows[i]);
}
}
return res;
}
vector<Mat> Matrices;
map<int, bitset<W>> obstacles;
vector<bitset<W>> aviable;
vector<bool> found;
bitset<W> all_aviable(bitset<mw> lh, bitset<mw> rh){
int id = lh.to_ullong() + rh.to_ullong() * W;
if(found[id]){
return aviable[id];
}
found[id] = true;
//cout<<lh<<" "<<rh<<endl;
for(int i = 0; i<w-1; i++){
if((!lh[i]) && (!rh[i+1])){
//cout<<"possible "<<i<<endl;
lh.set(i);
rh.set(i+1);
if(!rh[i]){
rh.set(i);
aviable[id] |= all_aviable(lh, rh);
rh.reset(i);
}
if(!lh[i+1]){
lh.set(i+1);
aviable[id]|= all_aviable(lh, rh);
lh.reset(i+1);
}
lh.reset(i);
rh.reset(i+1);
}
if((!lh[i+1]) && (!rh[i])){
rh.set(i);
lh.set(i+1);
if(!lh[i]){
lh.set(i);
aviable[id] |= all_aviable(lh, rh);
lh.reset(i);
}
if(!rh[i+1]){
rh.set(i+1);
aviable[id]|= all_aviable(lh, rh);
rh.reset(i+1);
}
rh.reset(i);
lh.reset(i+1);
}
}
return aviable[id];
}
vector<bitset<W>> interest;
signed main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int h, k;
cin>>w>>h>>k;
aviable.resize(W*W);
found.resize(W*W);
bitset<W> lh;
for(int i = 0; i<w; i++){
lh.set(i);
}
for(int rh = 0; rh<W; rh++){
int id = lh.to_ullong() + rh*W;
aviable[id].set(rh);
found[id] =true;
}
Mat transition;
for(int lhi = 0; lhi<W; lhi++){
interest.push_back(all_aviable(bitset<mw>(lhi), bitset<mw>(0)));
for(int rh = 0; rh<W; rh++){
transition.v[lhi][rh] = interest[lhi][rh];
}
}
pows[0] = transition;
precalc_pows();
for(int i = 0; i<k; i++){
int a, b;
cin>>a>>b;
a--;
b--;
obstacles[b].set(a);
}
obstacles[h-1] = bitset<W>(0);
Mat res = mpow(h-1);
if(res.v[0][(1<<w)-1]){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2761 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2747 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2752 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2738 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2766 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2761 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
