Submission #571688

#	Time	Username	Problem	Language	Result	Execution time	Memory
571688		8e7	IOI Fever (JOI21_fever)	C++17	37 / 100	5105 ms	66956 KiB

fever

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk 
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define x first
#define y second
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1e9 + 7;
pii a[maxn];
unordered_map<int, set<pii> > horz[4], vert[4], ru[4], rd[4];
unordered_map<ll, int> mp;
ll h(pii p) {
	return (ll)inf * p.x + p.y;
}
struct pnt{
	pii p;
	int t, d;
	pnt(){t = d = 0;}
	pnt(pii P, int ti, int di){p = P, t = ti, d = di;}
};
int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int movru[4][2] = {{1, 1}, {1, 1}, {-1, -1}, {-1, -1}};
int movrd[4][2] = {{1, -1}, {-1, 1}, {-1, 1}, {1, -1}};

int mind[maxn][3], di[maxn];
bool vis[maxn];
int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i].x >> a[i].y;
		a[i].x *= 2, a[i].y *= 2;
		mp[h(a[i])] = i;		
	}
	int ans = 0;
	for (int init_d = 0;init_d < 4;init_d++) {
		for (int i = 0;i < 4;i++) {
			horz[i].clear(), vert[i].clear(), ru[i].clear(), rd[i].clear();
		}
		for (int i = 0;i < n;i++) {
			mind[i][0] = mind[i][1] = mind[i][2] = inf;
			vis[i] = 0;
			if (i == 0) continue;
			int dx = a[i].x - a[0].x, dy = a[i].y - a[0].y;
			if (abs(dx) > abs(dy)) {
				di[i] = dx > 0 ? 2 : 0;
			} else if (abs(dx) < abs(dy)) {
				di[i] = dy > 0 ? 3 : 1;
			} else {
				pii tmp = {dx, dy};		
				for (int j = 0;j < 4 - init_d;j++) tmp = {-tmp.y, tmp.x};
				if (tmp.x > 0) di[i] = tmp.y > 0 ? 3 : 1;
				else di[i] = 0;
				di[i] = (di[i] + init_d)%4;
			}
			if (di[i] % 2) {
				vert[di[i]][a[i].x].insert(a[i]);
			} else {
				horz[di[i]][a[i].y].insert(a[i]);
			}
			ru[di[i]][a[i].x - a[i].y].insert(a[i]);
			rd[di[i]][a[i].x + a[i].y].insert(a[i]);
		}
		mind[0][0] = 0;
		di[0] = init_d;


		auto col = [&] (int i, int j) {
			int dx = a[j].x - a[i].x, dy = a[j].y - a[i].y;			
			int divx = mov[di[i]][0] - mov[di[j]][0], divy = mov[di[i]][1] - mov[di[j]][1];
			if (dx && divx == 0) return -1;	
			if (dy && divy == 0) return -1;	
			if (dx == 0) {
				if (abs(di[i] - di[j]) == 2) return dy / divy;
				return -1;
			}
			if (dy == 0) {
				if (abs(di[i] - di[j]) == 2) return dx / divx;
				return -1;
			}
			if (dx * divy != dy * divx) return -1;
			return dx / divx;
		};
		

		priority_queue<pii, vector<pii>, greater<pii> > pq;
		pq.push({0, 0});
		pii cur;
		int id, prv = 0, ti;

		auto relax = [&](pii p, int d, int val) {
			int ind = mp[h(p)];
			if (val >= ti && val < mind[ind][d]) {
				mind[ind][d] = val;
				pq.push({val, ind * 3 + d});
			}
		};
		auto upd = [&] (set<pii> &se, auto it, int d, bool type) {
			auto iter = se.begin();
			vector<pii> tmp;
			if (type == 0) {
				while (iter != it) {
					tmp.push_back(*iter);
					iter = next(iter);
				}
			} else {
				iter = it;
				while (iter != se.end()) {
					tmp.push_back(*iter);
					iter = next(iter);
				}
			}
			for (auto p:tmp) relax(p, d, col(id, mp[h(p)]));
			/*
			pii p;
			if (type == 0) {
				if (it != se.begin()) {
					p = *prev(it);
				} else {
					return;
				}
			} else {
				if (it != se.end()) {
					p = *it;
				} else {
					return;
				}
			}
			relax(p, d, col(id, mp[h(p)]));
			*/
		};
		auto to = [&] (set<pii> &se, bool type) { //0:prev, 1:next
			auto it = se.lower_bound(cur);
			pii q;	
			if (type && next(it) != se.end()) {
				q = *next(it);	
			} else if (type == 0 && it != se.begin()) {
				q = *prev(it);
			}
			int val = (abs(q.y - cur.y) + abs(q.x - cur.x)) / 2;
			relax(q, prv, ti + val);
		};
		while (pq.size()) {
			id = pq.top().ss / 3, prv = pq.top().ss % 3;
			ti = pq.top().ff;
			pq.pop();
			if (ti != mind[id][prv]) continue;
			debug("cur", id, prv, ti, di[id]);
			cur = a[id];
			vis[id] = 1;
			int dir = di[id];
			pii pos = {cur.x + mov[dir][0] * ti, cur.y + mov[dir][1] * ti};
			if (dir % 2 == 0) {
				auto se = horz[(dir+2)%4][pos.y];
				if (dir == 0) upd(se, se.lower_bound(pos), 0, 1);
				else upd(se, se.upper_bound(pos), 0, 0);
			} else {
				auto se = vert[(dir+2)%4][pos.x];
				if (dir == 1) upd(se, se.lower_bound(pos), 0, 1);
				else upd(se, se.upper_bound(pos), 0, 0);
			}
			pos = {cur.x + movru[dir][0] * ti, cur.y + movru[dir][1] * ti};
			auto se = ru[(3 - dir)][pos.x - pos.y];
			if (dir < 2) upd(se, se.lower_bound(pos), 1, 1);
			else upd(se, se.upper_bound(pos), 1, 0);

			pos = {cur.x + movrd[dir][0] * ti, cur.y + movrd[dir][1] * ti};
			se = rd[(dir < 2 ? 1 - dir : 5 - dir)][pos.x + pos.y];
			if (dir == 0 || dir == 3) upd(se, se.lower_bound(pos), 2, 1);	
			else upd(se, se.upper_bound(pos), 2, 0);	
			
			if (id == 0) continue;
			if (prv == 0) {
				if (dir % 2 == 0) to(horz[dir][cur.y], dir == 2);
				else to(vert[dir][cur.x], dir == 3);
			} else if (prv == 1) {
				to(ru[dir][cur.x - cur.y], dir >= 2);
			} else {
				to(rd[dir][cur.x + cur.y], dir == 1 || dir == 2);
			}
		}
		int cnt = 0;
		for (int i = 0;i < n;i++) {
			if (vis[i]) cnt++;
		}
		ans = max(ans, cnt);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
fever.cpp:164:4: note: in expansion of macro 'debug'
  164 |    debug("cur", id, prv, ti, di[id]);
      |    ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31