Submission #579030

#	Time	Username	Problem	Language	Result	Execution time	Memory
579030		MetalPower	IOI Fever (JOI21_fever)	C++14	69 / 100	2360 ms	90860 KiB

fever

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

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

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

ll N, X[MX], Y[MX], direction[MX];

// Right, Down, Left, Up

map<ll, vector<pii>> vert[4], hori[4], incd[4], decd[4];
ll dist[MX * 3]; bool colored[MX], vis[MX * 3];

vector<pii> adj[MX * 3];
// node, weight

void buildEdge(vector<pii>& v, ll inc, ll dir){ // dir 0 line, 1 clockwise, 2 counterclockwise
	if(inc == 1){
		for(ll i = 1; i < v.size(); i++){
			ll w = (v[i].fi - v[i - 1].fi) / (dir == 0 ? 2ll : 1ll);
			adj[(ll) 3 * v[i - 1].se + dir].push_back({(ll) 3 * v[i].se + dir, w});
		}
	}else{
		for(ll i = v.size() - 1; i > 0; i--){
			ll w = (v[i].fi - v[i - 1].fi) / (dir == 0 ? 2ll : 1ll);
			adj[(ll) 3 * v[i].se + dir].push_back({(ll) 3 * v[i - 1].se + dir, w});
		}
	}
}

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

pii trav(vector<pii>& v, ll node, ll d, ll dir){
	ll idx = lower_bound(v.begin(), v.end(), make_pair(d, (ll) -1)) - v.begin();
	if(idx == v.size()) return make_pair(-1, 0);
	ll nxt = v[idx].se, mdist;
	mdist = (absol(X[node] - X[nxt]) + absol(Y[node] - Y[nxt])) / 2;
	return {nxt * 3 + dir, mdist};
}

pii dtrav(vector<pii>& v, ll node, ll d, ll dir){
	ll idx = lower_bound(v.begin(), v.end(), make_pair(d + 1, (ll) -1)) - v.begin() - 1;
	if(idx == -1) return make_pair(-1, 0);
	ll nxt = v[idx].se, mdist;
	mdist = (absol(X[node] - X[nxt]) + absol(Y[node] - Y[nxt])) / 2;
	return {nxt * 3 + dir, mdist};
}

ll solve(){

	memset(vis, 0, sizeof vis);
	for(ll i = 0; i < 3 * MX; i++){
		adj[i].clear();
		dist[i] = INF;
		if(i < MX) colored[i] = false;
	}

	direction[0] = 0;
	for(ll i = 1; i < N; i++){
		ll _x = X[i] / 2, _y = Y[i] / 2;
		if(_x < 0 && (_y <= 0 ? -_y <= -_x : _y <= -_x)) direction[i] = 0;
		else if(_y > 0 && (_x <= 0 ? -_x <= _y - 1 : _x <= _y)) direction[i] = 1;
		else if(_x > 0 && (_y <= 0 ? -_y <= _x - 1 : _y <= _x - 1)) direction[i] = 2;
		else if(_y < 0 && (_x <= 0 ? -_x <= -_y - 1 : _x <= -_y)) direction[i] = 3;
		else assert(false);
	}

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

	for(ll i = 0; i < N; i++){
		vert[direction[i]][X[i]].push_back({Y[i], i});
		hori[direction[i]][Y[i]].push_back({X[i], i});
		incd[direction[i]][X[i] - Y[i]].push_back({X[i], i});
		decd[direction[i]][X[i] + Y[i]].push_back({X[i], i});
	}

	for(ll d = 0; d < 4; d++){
		for(auto& x : vert[d]) sort(x.se.begin(), x.se.end());
		for(auto& x : hori[d]) sort(x.se.begin(), x.se.end());
		for(auto& x : incd[d]) sort(x.se.begin(), x.se.end());
		for(auto& x : decd[d]) sort(x.se.begin(), x.se.end());
	}

	// Right, Down, Left, Up
	{
		for(auto& x : hori[0]) buildEdge(x.se, 0, 0);
		for(auto& x : vert[1]) buildEdge(x.se, 1, 0); 
		for(auto& x : hori[2]) buildEdge(x.se, 1, 0);
		for(auto& x : vert[3]) buildEdge(x.se, 0, 0);
	}

	{
		for(auto& x : incd[0]) buildEdge(x.se, 0, 2);
		for(auto& x : incd[1]) buildEdge(x.se, 1, 1);
		for(auto& x : incd[2]) buildEdge(x.se, 1, 2);
		for(auto& x : incd[3]) buildEdge(x.se, 0, 1);
	}

	{
		for(auto& x : decd[0]) buildEdge(x.se, 0, 1);
		for(auto& x : decd[1]) buildEdge(x.se, 0, 2);
		for(auto& x : decd[2]) buildEdge(x.se, 1, 1);
		for(auto& x : decd[3]) buildEdge(x.se, 1, 2);
	}

	priority_queue<pii, vector<pii>, greater<pii>> pq;

	pq.push({0, 0});
	dist[0] = 0;

	ll cnt = 0;

	while(!pq.empty()){

		// place-holder node
		ll cd = pq.top().fi; ll pd = pq.top().se; pq.pop();
		
		if(!vis[pd]){ // Reachable edge
			vis[pd] = true;
			for(auto nxt : adj[pd]){
				ll nd = cd + nxt.se;
				if(dist[nxt.fi] > nd){
					dist[nxt.fi] = nd;
					pq.push({dist[nxt.fi], nxt.fi});
				}
			}
		}

		// Right, Down, Left, Up

		ll node = pd / 3;
		if(!colored[node]){ // isColored
			// find collision

			pii nxt = {-1, 0};

			if(direction[node] == 0){

				nxt = trav(hori[2][Y[node]], node, X[node] + (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(incd[1][X[node] - Y[node]], node, X[node] + dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(decd[3][X[node] + Y[node]], node, X[node] + dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}else if(direction[node] == 1){

				nxt = dtrav(vert[3][X[node]], node, Y[node] - (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(decd[2][X[node] + Y[node]], node, X[node] + dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(incd[0][X[node] - Y[node]], node, X[node] - dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}else if(direction[node] == 2){

				nxt = dtrav(hori[0][Y[node]], node, X[node] - (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(incd[3][X[node] - Y[node]], node, X[node] - dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(decd[1][X[node] + Y[node]], node, X[node] - dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}else if(direction[node] == 3){

				nxt = trav(vert[1][X[node]], node, Y[node] + (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(decd[0][X[node] + Y[node]], node, X[node] - dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(incd[2][X[node] - Y[node]], node, X[node] + dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}

			colored[node] = true;
			cnt++;
		}
	}

	return cnt;
}

void rotate(){
	for(ll i = 0; i < N; i++){
		swap(X[i], Y[i]);
		Y[i] = -Y[i];
	}
}

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] <<= 1, Y[i] <<= 1;
		if(i != 0) X[i] -= X[0], Y[i] -= Y[0];
	}
	X[0] = Y[0] = 0;

	ll ans = 0;
	for(ll i = 0; i < 4; i++){
		ans = max(ans, solve());
		rotate();
	}

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

Compilation message (stderr)

fever.cpp: In function 'void buildEdge(std::vector<std::pair<long long int, long long int> >&, long long int, long long int)':
fever.cpp:25:19: 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]
   25 |   for(ll i = 1; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
fever.cpp: In function 'std::pair<long long int, long long int> trav(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
fever.cpp:43:9: 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]
   43 |  if(idx == v.size()) return make_pair(-1, 0);
      |     ~~~~^~~~~~~~~~~

• 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: 0 / 31