Submission #734440

#	Time	Username	Problem	Language	Result	Execution time	Memory
734440		QwertyPi	IOI Fever (JOI21_fever)	C++14	11 / 100	9 ms	12116 KiB

fever

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end() 
using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int INF = 1 << 30;
const int N = 1e5 + 11;
const int B = 5;
struct point{
	int x, y, d, id;
};

vector<point> P;
vector<pair<int, int>> G[N * B];
int collide(int a, int b){
	if(P[a].d == P[b].d) return INF;
	if((P[a].d ^ P[b].d) == 1){
		switch(P[a].d){
			case 0: return P[a].y == P[b].y && P[a].x < P[b].x ? (P[b].x - P[a].x) / 2 : INF;
			case 1: return P[a].y == P[b].y && P[b].x < P[a].x ? (P[a].x - P[b].x) / 2 : INF;
			case 2: return P[a].x == P[b].x && P[a].y < P[b].y ? (P[b].y - P[a].y) / 2 : INF;
			case 3: return P[a].x == P[b].x && P[b].y < P[a].y ? (P[a].y - P[b].y) / 2 : INF;
		}
		return INF;
	}
	if(abs(P[a].x - P[b].x) != abs(P[a].y - P[b].y)) return INF;
	int D = abs(P[a].x - P[b].x);
	if(P[a].x + P[a].y == P[b].x + P[b].y){
		if(P[a].x > P[b].x) swap(a, b);
		if((P[a].d == 0 && P[b].d == 2) || (P[a].d == 3 && P[b].d == 1)) return D;
		return INF;
	}else{
		if(P[a].x > P[b].x) swap(a, b);
		if((P[a].d == 0 && P[b].d == 3) || (P[a].d == 2 && P[b].d == 1)) return D;
		return INF;
	}
}

int ID(int x, int y = 0){
	return x * B + y;
}

int calc(){
	int n = P.size();
	vector<int> T(n * B, INF);
	for(int i = 0; i < n * B; i++) G[i].clear();
	
	for(int i = 0; i < n; i++){
		for(int j = 1; j < B; j++){
			G[i * B + j].push_back({i * B, 0});
		}
	}
	
	map<int, vector<pair<int, int>>> X, Y, A[4], M[4];
	for(auto p : P){
		X[p.x].push_back({p.y, p.id});
		Y[p.y].push_back({p.x, p.id});
		A[p.d][p.x + p.y].push_back({p.x, p.id});
		M[p.d][p.x - p.y].push_back({p.x, p.id});
	}
	
	for(int i = 0; i < 4; i++){
		for(auto& a : A[i]){
			vector<pair<int, int>>& r = a.second;
			sort(r.begin(), r.end());
			if(i == 0 || i == 3){
				for(int k = 0; k < (int) r.size() - 1; k++){
					G[ID(r[k + 1].second, 1)].push_back({ID(r[k].second, 1), abs(r[k].first - r[k + 1].first)});
				}
			}else{
				for(int k = 0; k < (int) r.size() - 1; k++){
					G[ID(r[k].second, 1)].push_back({ID(r[k + 1].second, 1), abs(r[k].first - r[k + 1].first)});
				}
			}
		}
		
		for(auto& m : M[i]){
			vector<pair<int, int>>& r = m.second;
			sort(r.begin(), r.end());
			if(i == 0 || i == 2){
				for(int k = 0; k < (int) r.size() - 1; k++){
					G[ID(r[k + 1].second, 2)].push_back({ID(r[k].second, 2), abs(r[k].first - r[k + 1].first)});
				}
			}else{
				for(int k = 0; k < (int) r.size() - 1; k++){
					G[ID(r[k].second, 2)].push_back({ID(r[k + 1].second, 2), abs(r[k].first - r[k + 1].first)});
				}
			}
		}
	}
	
	// Part A
	for(auto& a : A[0]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = A[2][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
			G[ID(id)].push_back({ID(ptr->se, 1), abs(x - ptr->fi)});
		}
	}
	
	for(auto& a : A[2]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = A[0][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
			G[ID(id)].push_back({ID(prev(ptr)->se, 1), abs(x - prev(ptr)->fi)});
		}
	}
	
	for(auto& a : A[1]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = A[3][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
			G[ID(id)].push_back({ID(prev(ptr)->se, 1), abs(x - prev(ptr)->fi)});
		}
	}
	
	for(auto& a : A[3]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = A[1][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
			G[ID(id)].push_back({ID(ptr->se, 1), abs(x - ptr->fi)});
		}
	}
	
	// Part M
	for(auto& a : M[0]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = M[3][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
			G[ID(id)].push_back({ID(ptr->se, 2), abs(x - ptr->fi)});
		}
	}
	
	for(auto& a : M[3]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = M[0][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
			G[ID(id)].push_back({ID(prev(ptr)->se, 2), abs(x - prev(ptr)->fi)});
		}
	}
	
	for(auto& a : M[1]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = M[2][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
			G[ID(id)].push_back({ID(prev(ptr)->se, 2), abs(x - prev(ptr)->fi)});
		}
	}
	
	for(auto& a : M[2]){
		vector<pair<int, int>>& r = a.second;
		auto& r2 = M[1][a.first];
		if(r2.empty()) continue;
		for(auto [x, id] : r){
			auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
			G[ID(id)].push_back({ID(ptr->se, 2), abs(x - ptr->fi)});
		}
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, 0}); T[0] = 0;
	while(!pq.empty()){
		auto [t, u] = pq.top(); pq.pop();
		if(T[u] != t) continue;
		for(auto [v, w] : G[u]) {
			if(v % B != 0 && u % B == 0){
				if(T[u] <= w && w < T[v]){
					T[v] = w;
					pq.push({T[v], v});
				}
			}else{
				if(T[u] + w < T[v]){
					T[v] = T[u] + w;
					pq.push({T[v], v});
				}
			}
		}
	}
	set<int> S;
	for(int i = 0; i < n * B; i++){
		if(T[i] != INF) S.insert(i / B);
	}
	int ans = S.size();
	return ans;
}

int32_t main(){
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		int x, y; cin >> x >> y; x *= 2, y *= 2;
		P.push_back({x, y, 0, i});
	}
	int ans = 0;
	for(int d0 = 0; d0 < 4; d0++){
		P[0].d = d0;
		for(int i = 1; i < n; i++){
			P[i].d = -1;
			int dx = P[i].x - P[0].x;
			int dy = P[i].y - P[0].y;
			if(dx == 0){
				P[i].d = 2 ^ (dy > 0);
			}else if(dy == 0){
				P[i].d = 0 ^ (dx > 0);
			}else{
				if(abs(dx) < abs(dy)){
					P[i].d = 2 ^ (dy > 0);
				}else if(abs(dy) < abs(dx)){
					P[i].d = 0 ^ (dx > 0);
				}else{
					if(P[0].d == 0 || P[0].d == 1) {
						if((P[0].d == 0) == (dx > 0)) P[i].d = 2 ^ (dy > 0);
						else P[i].d = P[0].d;
					}
					if(P[0].d == 2 || P[0].d == 3) {
						if((P[0].d == 2) == (dy > 0)) P[i].d = 0 ^ (dx > 0);
						else P[i].d = P[0].d;
					}
				}
			}
			assert(P[i].d != -1);
		}
		ans = max(ans, calc());
	}
	cout << ans << endl;
}

Compilation message (stderr)

fever.cpp: In function 'int calc()':
fever.cpp:100:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |   for(auto [x, id] : r){
      |            ^
fever.cpp:110:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |   for(auto [x, id] : r){
      |            ^
fever.cpp:120:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |   for(auto [x, id] : r){
      |            ^
fever.cpp:130:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |   for(auto [x, id] : r){
      |            ^
fever.cpp:141:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |   for(auto [x, id] : r){
      |            ^
fever.cpp:151:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |   for(auto [x, id] : r){
      |            ^
fever.cpp:161:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  161 |   for(auto [x, id] : r){
      |            ^
fever.cpp:171:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  171 |   for(auto [x, id] : r){
      |            ^
fever.cpp:179:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  179 |   auto [t, u] = pq.top(); pq.pop();
      |        ^
fever.cpp:181:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  181 |   for(auto [v, w] : G[u]) {
      |            ^

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