// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;}
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
namespace Map {
// from https://gist.github.com/Chillee/3bd6ee4429abb4a2e7c19959fb1490ae#file-hash-table-cpp
struct chash {
const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
static unsigned long long hash_f(pii p) {
unsigned long long x = p.first * 1000696969LL + p.second;
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
unsigned long long operator()(pii x) const { return hash_f(x) ^ RANDOM; }
};
typedef gp_hash_table<pii, int, chash> gp;
}
const int kN = 150051;
const int kB = kN * 9;
int n, t;
pii pos[kB];
Map::gp ids;
int tot = 0;
int skyToBlock[kN];
int blockToSky[kB];
bool built[kB];
int component[kB];
vector<int> inComponent[kB];
vector<int> G4[kB], G8[kB];
pii infinity(1e9 + 7, 1e9 + 7);
void newBlock(int r, int c) {
pii p(r, c);
auto it = ids.find(p);
if (it != end(ids)) return;
ids[p] = ++tot;
pos[tot] = p;
component[tot] = tot;
inComponent[tot].pb(tot);
}
bool isAP(int i) {
static bool has[3][3];
static int com[3][3];
static int cu, cd, cl, cr, ci;
for (int &j: G8[i]) {
int x = pos[j].ff - pos[i].ff + 1;
int y = pos[j].ss - pos[i].ss + 1;
has[x][y] = built[j];
com[x][y] = component[j];
}
cu = com[0][1]; cd = com[2][1];
cl = com[1][0]; cr = com[1][2];
if (!has[0][1] and !has[1][2] and cu == cr and
(has[0][0] or has[1][0] or has[2][0] or has[2][1] or has[2][2]))
return true;
if (!has[0][1] and !has[1][0] and cu == cl and
(has[0][2] or has[1][2] or has[2][0] or has[2][1] or has[2][2]))
return true;
if (!has[2][1] and !has[1][2] and cd == cr and
(has[0][0] or has[1][0] or has[2][0] or has[0][1] or has[0][2]))
return true;
if (!has[2][1] and !has[1][0] and cd == cl and
(has[0][2] or has[1][2] or has[2][2] or has[0][0] or has[0][1]))
return true;
if (!has[0][1] and !has[2][1] and cu == cd and
(has[0][0] or has[1][0] or has[2][0]) and
(has[0][2] or has[1][2] or has[2][2]))
return true;
if (!has[1][0] and !has[1][2] and cl == cr and
(has[0][0] or has[0][1] or has[0][2]) and
(has[2][0] or has[2][1] or has[2][2]))
return true;
ci = component[ids[infinity]];
if (cu == ci or cd == ci or cl == ci or cr == ci)
return false;
return true;
}
bool canErase[kN];
set<int, greater<int>> choose;
void updateSky(int i) {
bool ap = isAP(skyToBlock[i]);
if (ap and canErase[i])
choose.erase(i);
if (!ap and !canErase[i])
choose.insert(i);
canErase[i] = !ap;
}
// tissue is just a random name for timestamp
int lastUpdate[kN], tissue;
void merge(int i, int j, bool u) {
if (i == j) return;
if (inComponent[i].size() < inComponent[j].size())
swap(i, j);
for (int &v: inComponent[j]) {
component[v] = i;
inComponent[i].pb(v);
}
if (u) {
++tissue;
for (int &v: inComponent[j])
for (int &w: G8[v])
if (built[w] and lastUpdate[w] < tissue) {
lastUpdate[w] = tissue;
updateSky(skyToBlock[w]);
}
}
inComponent[j].clear();
}
bool vis[kB];
void dfs(int u, int &reach) {
++reach; vis[u] = true;
for (int &v: G8[u])
if (built[v] and !vis[v])
dfs(v, reach);
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> t;
for (int r, c, i = 1; i <= n; ++i) {
cin >> r >> c;
for (int dx = -1; dx <= 1; ++dx)
for (int dy = -1; dy <= 1; ++dy)
newBlock(r + dx, c + dy);
int id = ids[pii(r, c)];
skyToBlock[i] = id;
blockToSky[id] = i;
built[id] = true;
infinity = min(infinity, pii(r, c));
}
debug("Done 1");
for (int i = 1; i <= tot; ++i) {
auto &[r, c] = pos[i];
for (int dx = -1; dx <= 1; ++dx)
for (int dy = -1; dy <= 1; ++dy) {
if (dx == 0 and dy == 0) continue;
pii np(r + dx, c + dy);
auto it = ids.find(np);
if (it == end(ids)) continue;
int j = ids[np];
G8[i].pb(j);
if (dx == 0 or dy == 0) {
G4[i].pb(j);
if (!built[i] and !built[j])
merge(i, j, false);
}
}
}
debug("Done 2");
int reach = 0;
dfs(skyToBlock[1], reach);
if (reach != n) {
cout << "NO\n";
return 0;
}
debug("Done 3");
cout << "YES\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
95428 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
95428 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
95428 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
98608 KB |
ans=NO N=1934 |
| 2 |
Correct |
54 ms |
96580 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
49 ms |
95856 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
95428 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
115032 KB |
ans=NO N=66151 |
| 2 |
Correct |
573 ms |
168224 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
117 ms |
111172 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
98608 KB |
ans=NO N=1934 |
| 2 |
Correct |
54 ms |
96580 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
49 ms |
95856 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
