Submission #426200

#	Time	Username	Problem	Language	Result	Execution time	Memory
426200		Kevin_Zhang_TW	IOI Fever (JOI21_fever)	C++17	37 / 100	5038 ms	221132 KiB

fever

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
const ll inf = 1ll << 55;

int n;
int x[MAX_N], y[MAX_N];

ll dp[MAX_N * 4];
vector<pair<int,int>> edge[MAX_N * 4];

int dis(int i, int j) { return abs(x[i]-x[j]) + abs(y[i]-y[j]); }
pair<int,int> adv(int i, int dir, int j) {
	int a = x[i], b = y[i];
	if (dir == 0) a += j;
	if (dir == 1) b += j;
	if (dir == 2) a -= j;
	if (dir == 3) b -= j;
	return make_pair(a, b);
}

int gid(int i, int dir) { return i * 4 + dir; }

int oid[MAX_N][2][2];

void init() {
	int cnt = n * 4;
	for (int i = 0;i < n;++i)
		for (int j =0 ;j < 2;++j)
			for (int k = 0;k < 2;++k)
				oid[i][j][k] = cnt++;

	map<int, vector<tuple<int,int,int>>> mp;

	for (int i = 0;i < n;++i) {
		mp[ x[i]-y[i] ].pb( x[i], y[i], i );
	}
//
//	// need to modify to add
//	for (auto [_, vec] : mp) { 
//		sort(AI(vec));
//		for (int i = 0;i+1 < vec.size();++i) { 
//			auto [x, y, id] = vec[i];
//			auto [xx, yy, idd] = vec[i+1];
//			edge[ gid(id, 0) ].pb( oid[ idd ][0][0], xx-x ); 
//			edge[ gid(id, 1) ].pb( oid[ idd ][0][0], xx-x ); 
//			edge[ oid[id][0][0] ].pb( oid[idd][0][0], xx-x );
//
//			edge[ gid(idd, 2) ].pb( oid[id][0][1], xx-x );
//			edge[ gid(idd, 3) ].pb( oid[id][0][1], xx-x );
//			edge[ oid[idd][0][1] ].pb( oid[id][0][1], xx-x ); 
//		}
//
//		for (int i = 0;i < vec.size();++i) {
//			auto [x, y, id] = vec[i];
//			edge[ oid[id][0][0] ].pb( 
//		}
//	}

//	mp.clear();
//	for (int i = 0;i < n;++i) {
//		mp[ x[i]+y[i] ].pb( x[i], y[i], i );
//	}
//
//	for (auto [_, vec] : mp) { 
//		sort(AI(vec));
//		for (int i = 0;i+1 < vec.size();++i) { 
//			auto [x, y, id] = vec[i];
//			auto [xx, yy, idd] = vec[i+1];
//			edge[ gid(id, 0) ].pb( oid[ idd ][0][0], xx-x ); 
//			edge[ oid[id][0][0] ].pb( oid[idd][0][0], xx-x );
//
//			edge[ gid(idd, 2) ].pb( oid[id][0][1], xx-x );
//			edge[ oid[idd][0][1] ].pb( oid[id][0][1], xx-x ); 
//		}
//	}
	
	for (int i = 0;i < n;++i)
		for (int j = i+1;j < n;++j) {
			for (int k = 0;k < 4;++k)
				for (int l = 0;l < 4;++l) {
					int h = dis(i, j) / 2;
					if (adv(i, k, h) == adv(j, l, h)) {
						int a = i * 4 + k, b = j * 4 + l;
						edge[a].pb(b, h);
						edge[b].pb(a, h);
					} 
				} 
		}
}

int solve(int d) {
	fill(dp, dp + n * 4 * 2, inf);
	//priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;

	queue<pair<ll,ll>> pq;

	auto upd = [&](int id, ll t) {
		if (chmin(dp[id], t))
			pq.emplace(t, id);
	};

	upd(d, 0);
	while (pq.size()) {
		//auto [t, id] = pq.top(); pq.pop();
		auto [t, id] = pq.front(); pq.pop();
		if (t != dp[id]) continue;
		if (id < n * 4) for (auto [u, w] : edge[id]) {
			if (w >= t)
				upd(u, w); 
		} 
		else for (auto [u, w] : edge[id]) {
			upd(u, w + t);
		}
	} 

	int res = 0;
	for (int i = 0;i < n;++i) {
		ll d = inf;
		for (int j = 0;j < 4;++j)
			chmin(d, dp[i * 4 + j]);
		if (d < inf) ++res;
	}
	return res;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0;i < n;++i) cin >> x[i] >> y[i], x[i] *= 2, y[i] *= 2;

	init();

	int res = 1;
	for (int i = 0;i < 4;++i)
		chmax(res, solve(i));

	cout << res << '\n'; 
} 

• 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