| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122764 |
2019-06-29T09:03:20 Z |
윤교준(#3000) |
Golf (JOI17_golf) |
C++14 |
|
62 ms |
31884 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
inline void fg(vector<pii> G[], int a, int b, int c) { G[a].eb(b, c); G[b].eb(a, c); }
const int MAXN = 100055;
const int MAXK = MAXN*3*4;
struct LNEEVT {
LNEEVT(ll x, ll sy, ll ey)
: x(x), sy(sy), ey(ey) {}
ll x, sy, ey;
bool operator < (const LNEEVT &t) const {
return x < t.x;
}
};
vector<pii> G[MAXK];
int DP[MAXK];
int K, Sidx, Eidx;
vector<pair<pll, pll>> EDV;
vector<pll> PV;
ll SX[MAXN], SY[MAXN], EX[MAXN], EY[MAXN];
ll MNSX, MXSX, MNSY, MXSY;
ll MNEX, MXEX, MNEY, MXEY;
ll PSX, PSY, PEX, PEY;
int N, Ans = INF;
inline int getI(const pll &p) { return int(lower_bound(allv(PV), p) - PV.begin()); }
inline int getDr(const pll &a, const pll &b) {
if(a.first == b.first) return a.second < b.second ? 0 : 2;
return a.first < b.first ? 1 : 3;
}
inline bool isCross(ll ax, ll asy, ll aey, ll bsx, ll bex, ll by) {
return bsx <= ax && ax <= bex && asy <= by && by <= aey;
}
bool isPathOK(pll a, pll b) {
if(a.first == b.first) {
if(a.second > b.second) swap(a, b);
for(int i = 1; i <= N; i++) {
if(isCross(a.first, a.second, b.second, SX[i]+1, EX[i]-1, SY[i]+1)) return false;
if(isCross(a.first, a.second, b.second, SX[i]+1, EX[i]-1, EY[i]-1)) return false;
}
return true;
}
if(a.first > b.first) swap(a, b);
for(int i = 1; i <= N; i++) {
if(isCross(SX[i]+1, SY[i]+1, EY[i]-1, a.first, b.first, a.second)) return false;
if(isCross(EX[i]-1, SY[i]+1, EY[i]-1, a.first, b.first, a.second)) return false;
}
return true;
}
bool isAnswerOne() {
if(PSX != PEX && PSY != PEY) return false;
return isPathOK({PSX, PSY}, {PEX, PEY});
}
bool isAnswerTwo() {
return (isPathOK({PSX, PSY}, {PSX, PEY}) && isPathOK({PSX, PEY}, {PEX, PEY}))
|| (isPathOK({PSX, PSY}, {PEX, PSY}) && isPathOK({PEX, PSY}, {PEX, PEY}));
}
bool tryForThree(ll sx, ll ex, ll sy, ll ey, vector<pll> &V) {
if(sy > ey) return false;
if(V.empty()) return true;
vector<ll> YV;
YV.eb(sy); YV.eb(ey); YV.eb(ey+1);
for(auto &v : V) {
YV.eb(v.first);
YV.eb(v.second+1);
}
sorv(YV); univ(YV);
int n = sz(YV);
vector<int> S(n, 0);
for(auto &v : V) {
S[int(lower_bound(allv(YV), v.first) - YV.begin())]++;
S[int(lower_bound(allv(YV), v.second+1) - YV.begin())]--;
}
if(!S[0]) return true;
for(int i = 1; i < n-1; i++) {
S[i] += S[i-1];
if(!S[i]) return true;
}
return false;
}
bool isAnswerThree() {
{
vector<pll> V;
ll mn = max(MNSY, MNEY), mx = min(MXSY, MXEY);
for(int i = 1; i <= N; i++) {
if(PSX <= SX[i]+1 && SX[i]+1 <= PEX) {
ll s = max(SY[i]+1, mn), e = min(EY[i]-1, mx);
if(s <= e) V.eb(s, e);
}
}
if(tryForThree(PSX, PEX, mn, mx, V)) return true;
}
{
vector<pll> V;
ll mn = max(MNSX, MNEX), mx = min(MXSX, MXEX);
for(int i = 1; i <= N; i++) {
if(PSY <= SY[i]+1 && SY[i]+1 <= PEY) {
ll s = max(SX[i]+1, mn), e = min(EX[i]-1, mx);
if(s <= e) V.eb(s, e);
}
}
if(tryForThree(PSY, PEY, mn, mx, V)) return true;
}
return false;
}
void findMNMXXY() {
MNSX = MNSY = MNEX = MNEY = -INFLL;
MXSX = MXSY = MXEX = MXEY = INFLL;
for(int i = 1; i <= N; i++) {
if(SX[i] <= PSX && PSX <= EX[i]) {
if(PSY <= SY[i]) upmin(MXSY, SY[i]);
if(EY[i] <= PSY) upmax(MNSY, EY[i]);
}
if(SY[i] <= PSY && PSY <= EY[i]) {
if(PSX <= SX[i]) upmin(MXSX, SX[i]);
if(EX[i] <= PSX) upmax(MNSX, EX[i]);
}
if(SX[i] <= PEX && PEX <= EX[i]) {
if(PEY <= SY[i]) upmin(MXEY, SY[i]);
if(EY[i] <= PEY) upmax(MNEY, EY[i]);
}
if(SY[i] <= PEY && PEY <= EY[i]) {
if(PEX <= SX[i]) upmin(MXEX, SX[i]);
if(EX[i] <= PEX) upmax(MNEX, EX[i]);
}
}
}
void makePoints(vector<LNEEVT> &EV, vector<pll> &PV) {
set<ll> CH;
sorv(EV);
for(auto &ev : EV) {
ll s = ev.sy, e = ev.ey, x = ev.x;
PV.eb(x, s); PV.eb(x, e);
for(auto it = CH.lower_bound(s); CH.end() != it && *it <= e;) {
PV.eb(x, *it);
it = CH.erase(it);
}
CH.insert(s); CH.insert(e);
}
}
void makePoints() {
PV.eb(PSX, PSY); PV.eb(PEX, PEY);
if(-INFLL < MNSX) PV.eb(MNSX, PSY);
if(MXSX < INFLL) PV.eb(MXSX, PSY);
if(-INFLL < MNSY) PV.eb(PSX, MNSY);
if(MXSY < INFLL) PV.eb(PSX, MXSY);
if(-INFLL < MNEX) PV.eb(MNEX, PEY);
if(MXEX < INFLL) PV.eb(MXEX, PEY);
if(-INFLL < MNEY) PV.eb(PEX, MNEY);
if(MXEY < INFLL) PV.eb(PEX, MXEY);
{
vector<LNEEVT> EV;
vector<pll> V;
for(int i = 1; i <= N; i++) {
EV.eb(SX[i], SY[i], EY[i]);
EV.eb(EX[i], SY[i], EY[i]);
}
makePoints(EV, V);
for(auto &v : V) PV.eb(v.first, v.second);
}
{
vector<LNEEVT> EV;
vector<pll> V;
for(int i = 1; i <= N; i++) {
EV.eb(-SX[i], SY[i], EY[i]);
EV.eb(-EX[i], SY[i], EY[i]);
}
makePoints(EV, V);
for(auto &v : V) PV.eb(-v.first, v.second);
}
{
vector<LNEEVT> EV;
vector<pll> V;
for(int i = 1; i <= N; i++) {
EV.eb(SY[i], SX[i], EX[i]);
EV.eb(EY[i], SX[i], EX[i]);
}
makePoints(EV, V);
for(auto &v : V) PV.eb(v.second, v.first);
}
{
vector<LNEEVT> EV;
vector<pll> V;
for(int i = 1; i <= N; i++) {
EV.eb(-SY[i], SX[i], EX[i]);
EV.eb(-EY[i], SX[i], EX[i]);
}
makePoints(EV, V);
for(auto &v : V) PV.eb(v.second, -v.first);
}
sorv(PV); univ(PV);
}
void makeEdges(vector<pll> &PV, vector<pll> &BV, vector<pair<pll, pll>> &EV) {
set<ll> CH;
sorv(PV); sorv(BV);
for(int s = 0, e, pv = 0, n = sz(PV), m = sz(BV); s < n;) {
if(pv < m && BV[pv] < PV[s]) {
auto it = CH.find(BV[pv].second);
if(CH.end() != it) CH.erase(it);
else CH.insert(BV[pv].second);
pv++;
continue;
}
for(e = s+1; e < n && PV[s].first == PV[e].first; e++);
auto it = CH.begin();
for(int i = s+1; i < e; i++) {
for(; CH.end() != it && *it < PV[i-1].second; it++);
if(CH.end() == it || PV[i].second < *it) EV.eb(PV[i-1], PV[i]);
}
s = e;
}
}
void makeEdges() {
{
vector<pair<pll, pll>> EV;
vector<pll> BV;
for(int i = 1; i <= N; i++) {
if(SX[i]+2 == EX[i]) continue;
BV.eb(SX[i]+1, SY[i]+1);
BV.eb(SX[i]+1, EY[i]-1);
if(SY[i]+2 < EY[i]) {
BV.eb(EX[i]-1, SY[i]+1);
BV.eb(EX[i]-1, EY[i]-1);
}
}
makeEdges(PV, BV, EV);
for(auto &ed : EV) {
if(ed.first > ed.second) swap(ed.first, ed.second);
EDV.eb(ed);
}
}
{
vector<pair<pll, pll>> EV;
vector<pll> BV;
for(auto &v : PV) swap(v.first, v.second);
for(int i = 1; i <= N; i++) {
if(SY[i]+2 == EY[i]) continue;
BV.eb(SY[i]+1, SX[i]+1);
BV.eb(SY[i]+1, EX[i]-1);
if(SX[i]+2 < EX[i]) {
BV.eb(EY[i]-1, SX[i]+1);
BV.eb(EY[i]-1, EX[i]-1);
}
}
makeEdges(PV, BV, EV);
for(auto &v : PV) swap(v.first, v.second);
sorv(PV);
for(auto &ed : EV) {
swap(ed.first.first, ed.first.second);
swap(ed.second.first, ed.second.second);
if(ed.first > ed.second) swap(ed.first, ed.second);
EDV.eb(ed);
}
}
sorv(EDV); univ(EDV);
}
void makeGraph() {
K = sz(PV) << 2;
fill(DP, DP+K, INF);
Sidx = getI({PSX, PSY});
Eidx = getI({PEX, PEY});
for(int i = 0; i < 4; i++) DP[(Sidx<<2)|i] = 1;
for(int i = 0; i < K; i += 4) {
for(int a = 0; a < 4; a++) for(int b = a+1; b < 4; b++)
fg(G, i|a, i|b, 1);
}
for(auto &ed : EDV) {
int a = getI(ed.first), b = getI(ed.second);
int dr = getDr(ed.first, ed.second);
G[(a<<2)|dr].eb((b<<2)|dr, 0);
G[(b<<2)|(dr^2)].eb((a<<2)|(dr^2), 0);
}
}
void spreadStarts() {
// TODO for O(N lgN)
for(int i = sz(PV); i--;) {
const pll &p = PV[i];
if(MNSX <= p.first && p.first <= MXSX && p.second != PSY) {
if(isPathOK({PSX, PSY}, {p.first, PSY}) && isPathOK({p.first, PSY}, p)) {
if(PSY < p.second) upmin(DP[i<<2], 2);
else upmin(DP[(i<<2)|2], 2);
}
}
if(MNSY <= p.second && p.second <= MXSY && p.first != PSX) {
if(isPathOK({PSX, PSY}, {PSX, p.second}) && isPathOK({PSX, p.second}, p)) {
if(PSX < p.first) upmin(DP[(i<<2)|1], 2);
else upmin(DP[(i<<2)|3], 2);
}
}
}
}
void runDijk() {
priority_queue<pii, vector<pii>, greater<pii>> PQ;
for(int i = 0; i < K; i++) if(DP[i] < 3) PQ.push({DP[i], i});
for(int idx, dst; !PQ.empty();) {
tie(dst, idx) = PQ.top(); PQ.pop();
if(DP[idx] < dst) continue;
for(auto &ed : G[idx]) {
int nidx = ed.first;
int ndst = dst + ed.second;
if(DP[nidx] <= ndst) continue;
DP[nidx] = ndst;
PQ.push({ndst, nidx});
}
}
}
void calAns() {
for(int i = 0; i < 4; i++) upmin(Ans, DP[(Eidx<<2)|i]);
for(int i = sz(PV); i--;) {
const pll &p = PV[i];
if(MNEX <= p.first && p.first <= MXEX && p.second != PEY) {
if(isPathOK({PEX, PEY}, {p.first, PEY}) && isPathOK({p.first, PEY}, p)) {
if(PEY < p.second) upmin(Ans, DP[(i<<2)|2] + 1);
else upmin(Ans, DP[i<<2] + 1);
}
}
if(MNEY <= p.second && p.second <= MXEY && p.first != PEX) {
if(isPathOK({PEX, PEY}, {PEX, p.second}) && isPathOK({PEX, p.second}, p)) {
if(PEX < p.first) upmin(Ans, DP[(i<<2)|3] + 1);
else upmin(Ans, DP[(i<<2)|1] + 1);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> PSX >> PSY >> PEX >> PEY >> N;
PSX <<= 1; PSY <<= 1; PEX <<= 1; PEY <<= 1;
for(int i = 1; i <= N; i++) {
cin >> SX[i] >> EX[i] >> SY[i] >> EY[i];
SX[i] <<= 1; EX[i] <<= 1;
SY[i] <<= 1; EY[i] <<= 1;
}
if(PSX > PEX) {
PSX = -PSX; PEX = -PEX;
for(int i = 1; i <= N; i++) {
SX[i] = -SX[i];
EX[i] = -EX[i];
}
}
if(PSY > PEY) {
PSY = -PSY; PEY = -PEY;
for(int i = 1; i <= N; i++) {
SY[i] = -SY[i];
EY[i] = -EY[i];
}
}
for(int i = 1; i <= N; i++) {
if(SX[i] > EX[i]) swap(SX[i], EX[i]);
if(SY[i] > EY[i]) swap(SY[i], EY[i]);
}
{
ll mn = min({PSX, PEX, *min_element(SX+1, SX+N+1)});
PSX -= mn; PEX -= mn;
for(int i = 1; i <= N; i++) {
SX[i] -= mn;
EX[i] -= mn;
}
mn = min({PSY, PEY, *min_element(SY+1, SY+N+1)});
PSY -= mn; PEY -= mn;
for(int i = 1; i <= N; i++) {
SY[i] -= mn;
EY[i] -= mn;
}
}
if(isAnswerOne()) {
puts("1");
exit(0);
}
if(isAnswerTwo()) {
puts("2");
exit(0);
}
findMNMXXY();
if(isAnswerThree()) {
puts("3");
exit(0);
}
makePoints();
makeEdges();
/*
for(auto &p : PV) printf("%lld %lld\n", p.first, p.second);
for(auto &ed : EDV) printf("%lld %lld <-> %lld %lld\n", ed.first.first, ed.first.second, ed.second.first, ed.second.second);
*/
makeGraph();
spreadStarts();
runDijk();
calAns();
cout << Ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
24 ms |
28544 KB |
Output is correct |
| 3 |
Correct |
22 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 5 |
Incorrect |
62 ms |
31884 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
24 ms |
28544 KB |
Output is correct |
| 3 |
Correct |
22 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 5 |
Incorrect |
62 ms |
31884 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
24 ms |
28544 KB |
Output is correct |
| 3 |
Correct |
22 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 5 |
Incorrect |
62 ms |
31884 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
