Submission #579234

#	Time	Username	Problem	Language	Result	Execution time	Memory
579234		MetalPower	IOI Fever (JOI21_fever)	C++14	100 / 100	1132 ms	201600 KiB

fever

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll MX = 3e5 + 10;
const ll INF = 1e18;

ll N, X[MX], Y[MX]; ll direction[MX];
ll dist[MX * 3]; bool vis[MX * 3], colored[MX * 3];
vector<pii> adj[MX * 3], hori[MX][4], vert[MX][4], incd[MX][4], decd[MX][4];
ll hx[MX], vx[MX], ix[MX], dx[MX];

ll absol(ll x){
	return x >= 0 ? x : -x;
}

void buildEdge(vector<pii>& v, ll st, ll dir){
	if(st == 0){ // increasing
		for(ll i = 1; i < (ll) v.size(); i++){
			// cout << "Edge " << v[i - 1].se * 3 + dir << " to " << v[i].se * 3 + dir << '\n';
			ll w = (v[i].fi - v[i - 1].fi) / (dir == 0 ? 2ll : 1ll);
			adj[v[i - 1].se * 3 + dir].push_back({v[i].se * 3 + dir, w});
		}
	}else{ // decreasing
		for(ll i = (ll) v.size() - 1; i > 0; i--){
			// cout << "Edge " << v[i].se * 3 + dir << " to " << v[i - 1].se * 3 + dir << '\n';
			ll w = (v[i].fi - v[i - 1].fi) / (dir == 0 ? 2ll : 1ll);
			adj[v[i].se * 3 + dir].push_back({v[i - 1].se * 3 + dir, w});
		}
	}
}

ll que(vector<pii>& v, ll dt, ll tp){
	if(tp == 1){
		return (ll)(lower_bound(v.begin(), v.end(), make_pair(dt, (ll) -1)) - v.begin());
	}else if(tp == -1){
		return (ll)(lower_bound(v.begin(), v.end(), make_pair(dt + 1, (ll) -1)) - v.begin()) - 1;
	}
}

ll solve(){
	{ // initialize
		for(ll i = 0; i < MX * 3; i++){
			dist[i] = INF;
			vis[i] = colored[i] = false;
			adj[i].clear();
		}

		for(ll i = 0; i < MX; i++){
			for(ll d = 0; d < 4; d++){
				hori[i][d].clear();
				vert[i][d].clear();
				incd[i][d].clear();
				decd[i][d].clear();
			}
		}

		// cout << "initialize" << '\n';
	}

	{ // Right, Up, Left, Down
		direction[0] = 0;
		for(ll i = 1; i < N; i++){
			if(absol(X[i]) == absol(Y[i])){
				if(X[i] < 0) direction[i] = 0;
				else if(X[i] > 0 && Y[i] < 0) direction[i] = 1;
				else if(X[i] > 0 && Y[i] > 0) direction[i] = 3;
			}else if(absol(X[i]) < absol(Y[i])){
				if(Y[i] < 0) direction[i] = 1;
				else if(Y[i] > 0) direction[i] = 3;
			}else if(absol(X[i]) > absol(Y[i])){
				if(X[i] < 0) direction[i] = 0;
				else if(X[i] > 0) direction[i] = 2;
			}
		}
	}

	{
		vector<ll> hv, vv, iv, dv;

		for(ll i = 0; i < N; i++){
			hv.push_back(Y[i]);
			vv.push_back(X[i]);
			iv.push_back(X[i] - Y[i]);
			dv.push_back(X[i] + Y[i]);
		}

		// cout << "coordinate compress" << '\n';

		sort(hv.begin(), hv.end()); hv.resize(unique(hv.begin(), hv.end()) - hv.begin());
		sort(vv.begin(), vv.end()); vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
		sort(iv.begin(), iv.end()); iv.resize(unique(iv.begin(), iv.end()) - iv.begin());
		sort(dv.begin(), dv.end()); dv.resize(unique(dv.begin(), dv.end()) - dv.begin());

		// cout << "sort" << '\n';

		for(ll i = 0; i < N; i++){
			hx[i] = lower_bound(hv.begin(), hv.end(), Y[i]) - hv.begin();
			vx[i] = lower_bound(vv.begin(), vv.end(), X[i]) - vv.begin();
			ix[i] = lower_bound(iv.begin(), iv.end(), X[i] - Y[i]) - iv.begin();
			dx[i] = lower_bound(dv.begin(), dv.end(), X[i] + Y[i]) - dv.begin();
			hori[hx[i]][direction[i]].push_back({X[i], i}); 
			// cout << "hori " << hx[i] << " " << direction[i] << " node " << i << '\n';
			vert[vx[i]][direction[i]].push_back({Y[i], i});
			// cout << "vert " << vx[i] << " " << direction[i] << " node " << i << '\n';
			incd[ix[i]][direction[i]].push_back({X[i], i});
			// cout << "incd " << ix[i] << " " << direction[i] << " node " << i << '\n';
			decd[dx[i]][direction[i]].push_back({X[i], i});
			// cout << "decd " << dx[i] << " " << direction[i] << " node " << i << '\n';
		}

		// cout << "create groups" << '\n';

		for(ll i = 0; i < N; i++){
			for(ll d = 0; d < 4; d++){
				sort(hori[i][d].begin(), hori[i][d].end());
				sort(vert[i][d].begin(), vert[i][d].end());
				sort(incd[i][d].begin(), incd[i][d].end());
				sort(decd[i][d].begin(), decd[i][d].end());
			}
		}

		for(ll i = 0; i < N; i++){
			// Horizontal / Vertical
			buildEdge(hori[i][0], 1, 0);
			buildEdge(vert[i][1], 1, 0);
			buildEdge(hori[i][2], 0, 0);
			buildEdge(vert[i][3], 0, 0);

			// Increasing Diagonal
			buildEdge(incd[i][0], 1, 2);
			buildEdge(incd[i][1], 1, 1);
			buildEdge(incd[i][2], 0, 2);
			buildEdge(incd[i][3], 0, 1);

			// Decreasing Diagonal
			buildEdge(decd[i][0], 1, 1);
			buildEdge(decd[i][1], 0, 2);
			buildEdge(decd[i][2], 0, 1);
			buildEdge(decd[i][3], 1, 2);
		}

		// cout << "build edge" << '\n';
	}

	{

		priority_queue<pii, vector<pii>, greater<pii>> pq;
		pq.push({0, 0}); pq.push({0, 1}); pq.push({0, 2});

		while(!pq.empty()){
			ll cd = pq.top().fi, pd = pq.top().se; pq.pop();

			if(!vis[pd]){
				if(cd != 0) vis[pd] = true;
				for(pii nxt : adj[pd]){ // nxt.fi = node, nxt.se = weight
					ll nw = dist[pd] + nxt.se;
					if(dist[nxt.fi] > nw){
						dist[nxt.fi] = nw;
						pq.push({dist[nxt.fi], nxt.fi});
					}
				}
			}

			ll nd = pd / 3;
			if(!colored[nd]){

				colored[nd] = true; 

				{ // normal
					ll nxt = -1;
					if(direction[nd] == 0){
						ll idx = que(hori[hx[nd]][2], X[nd] + cd * 2, 1);
						if(0 <= idx && idx < hori[hx[nd]][2].size()) nxt = hori[hx[nd]][2][idx].se;
					}else if(direction[nd] == 1){
						ll idx = que(vert[vx[nd]][3], Y[nd] + cd * 2, 1);
						if(0 <= idx && idx < vert[vx[nd]][3].size()) nxt = vert[vx[nd]][3][idx].se;
					}else if(direction[nd] == 2){
						ll idx = que(hori[hx[nd]][0], X[nd] - cd * 2, -1);
						if(0 <= idx && idx < hori[hx[nd]][0].size()) nxt = hori[hx[nd]][0][idx].se;
					}else if(direction[nd] == 3){
						ll idx = que(vert[vx[nd]][1], Y[nd] - cd * 2, -1);
						if(0 <= idx && idx < vert[vx[nd]][1].size()) nxt = vert[vx[nd]][1][idx].se;
					}
					if(nxt != -1){
						// cout << "Collision " << X[nd] << " " << Y[nd] << " to " << X[nxt] << " " << Y[nxt] << '\n';
						ll ndist = (absol(X[nd] - X[nxt]) + absol(Y[nd] - Y[nxt])) / 2ll;
						if(dist[nxt * 3] > ndist){
							dist[nxt * 3] = ndist;
							pq.push({dist[nxt * 3], nxt * 3});
						}
					}
				}

				// cout << "normal" << '\n';
				// Right, Up, Left, Down

				{ // clockwise
					ll nxt = -1;
					if(direction[nd] == 0){
						ll idx = que(incd[ix[nd]][3], X[nd] + cd, 1);
						if(0 <= idx && idx < incd[ix[nd]][3].size()) nxt = incd[ix[nd]][3][idx].se;
					}else if(direction[nd] == 1){
						ll idx = que(decd[dx[nd]][0], X[nd] - cd, -1);
						if(0 <= idx && idx < decd[dx[nd]][0].size()) nxt = decd[dx[nd]][0][idx].se;
					}else if(direction[nd] == 2){
						ll idx = que(incd[ix[nd]][1], X[nd] - cd, -1);
						if(0 <= idx && idx < incd[ix[nd]][1].size()) nxt = incd[ix[nd]][1][idx].se;
					}else if(direction[nd] == 3){
						ll idx = que(decd[dx[nd]][2], X[nd] + cd, 1);
						if(0 <= idx && idx < decd[dx[nd]][2].size()) nxt = decd[dx[nd]][2][idx].se;
					}
					if(nxt != -1){
						// cout << "Collision " << X[nd] << " " << Y[nd] << " to" << X[nxt] << " " << Y[nxt] << '\n';
						ll ndist = (absol(X[nd] - X[nxt]) + absol(Y[nd] - Y[nxt])) / 2ll;
						if(dist[nxt * 3 + 1] > ndist){
							dist[nxt * 3 + 1] = ndist;
							pq.push({dist[nxt * 3 + 1], nxt * 3 + 1});
						}
					}
				}

				// cout << "clockwise" << '\n';

				{ // counter clockwise
					ll nxt = -1;
					if(direction[nd] == 0){
						ll idx = que(decd[dx[nd]][1], X[nd] + cd, 1);
						if(0 <= idx && idx < decd[dx[nd]][1].size()) nxt = decd[dx[nd]][1][idx].se;
					}else if(direction[nd] == 1){
						ll idx = que(incd[ix[nd]][2], X[nd] + cd, 1);
						if(0 <= idx && idx < incd[ix[nd]][2].size()) nxt = incd[ix[nd]][2][idx].se;
					}else if(direction[nd] == 2){
						ll idx = que(decd[dx[nd]][3], X[nd] - cd, -1);
						if(0 <= idx && idx < decd[dx[nd]][3].size()) nxt = decd[dx[nd]][3][idx].se;
					}else if(direction[nd] == 3){
						ll idx = que(incd[ix[nd]][0], X[nd] - cd, -1);
						if(0 <= idx && idx < incd[ix[nd]][0].size()) nxt = incd[ix[nd]][0][idx].se;
					}
					if(nxt != -1){
						// cout << "Collision " << X[nd] << " " << Y[nd] << " to" << X[nxt] << " " << Y[nxt] << '\n';
						ll ndist = (absol(X[nd] - X[nxt]) + absol(Y[nd] - Y[nxt])) / 2ll;
						if(dist[nxt * 3 + 2] > ndist){
							dist[nxt * 3 + 2] = ndist;
							pq.push({dist[nxt * 3 + 2], nxt * 3 + 2});
						}
					}
				}

				// cout << "counterclockwise" << '\n';
			}
		}

		ll res = 1;
		for(int i = 1; i < N; i++)
			if(min(dist[i * 3], min(dist[i * 3 + 1], dist[i * 3 + 2])) < INF) res++;
		return res;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for(ll i = 0; i < N; i++){
		cin >> X[i] >> Y[i]; X[i] *= 2, Y[i] *= 2;
		if(i > 0) X[i] -= X[0], Y[i] -= Y[0];
	}
	X[0] = Y[0] = 0;

	ll ans = 0;
	for(ll t = 0; t < 4; t++){
		ll curr = solve(); 
		ans = max(ans, curr);
		for(ll i = 0; i < N; i++){ // (x, y) = (y, -x)
			swap(X[i], Y[i]);
			Y[i] = -Y[i];
		}
	}

	cout << ans << '\n';
}

Compilation message (stderr)

fever.cpp: In function 'long long int solve()':
fever.cpp:178:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |       if(0 <= idx && idx < hori[hx[nd]][2].size()) nxt = hori[hx[nd]][2][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:181:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |       if(0 <= idx && idx < vert[vx[nd]][3].size()) nxt = vert[vx[nd]][3][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:184:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |       if(0 <= idx && idx < hori[hx[nd]][0].size()) nxt = hori[hx[nd]][0][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:187:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |       if(0 <= idx && idx < vert[vx[nd]][1].size()) nxt = vert[vx[nd]][1][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:206:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |       if(0 <= idx && idx < incd[ix[nd]][3].size()) nxt = incd[ix[nd]][3][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:209:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |       if(0 <= idx && idx < decd[dx[nd]][0].size()) nxt = decd[dx[nd]][0][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:212:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |       if(0 <= idx && idx < incd[ix[nd]][1].size()) nxt = incd[ix[nd]][1][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:215:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |       if(0 <= idx && idx < decd[dx[nd]][2].size()) nxt = decd[dx[nd]][2][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:233:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |       if(0 <= idx && idx < decd[dx[nd]][1].size()) nxt = decd[dx[nd]][1][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:236:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |       if(0 <= idx && idx < incd[ix[nd]][2].size()) nxt = incd[ix[nd]][2][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:239:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |       if(0 <= idx && idx < decd[dx[nd]][3].size()) nxt = decd[dx[nd]][3][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:242:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |       if(0 <= idx && idx < incd[ix[nd]][0].size()) nxt = incd[ix[nd]][0][idx].se;
      |                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp: In function 'long long int que(std::vector<std::pair<long long int, long long int> >&, long long int, long long int)':
fever.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^

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