Submission #521525

#	Time	Username	Problem	Language	Result	Execution time	Memory
521525		amunduzbaev	IOI Fever (JOI21_fever)	C++14	25 / 100	5031 ms	434736 KiB

fever

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 2>> p(n);
	for(int i=0;i<n;i++) cin>>p[i][0]>>p[i][1];
	map<int, deque<int>> m1, m2, x, y;
	for(int i=0;i<n;i++){
		m1[p[i][0] + p[i][1]].push_back(i);
		m2[p[i][0] - p[i][1]].push_back(i);
		x[p[i][0]].push_back(i);
		y[p[i][1]].push_back(i);
	}
	
	for(auto& [x, v] : m1){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
	} for(auto& [x, v] : m2){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
	} for(auto& [x, v] : x){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
	} for(auto& [x, v] : y){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][1] < p[j][1]); });
	}
	
	int ans = 0;
	for(int t=0;t<4;t++){
		auto t1 = m1, t2 = m2;
		vector<int> T(n, 1e18); T[0] = 0;
		priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> qq; 
		qq.push({0, t, 0}); int res = 0;
		while(!qq.empty()){
			auto u = qq.top(); qq.pop();
			int i = u[2], t = u[1];
			//~ if(u[0] > T[i]) continue;
			{
				auto& v = m1[p[i][0] + p[i][1]];
				auto tmp = v;
				while(!v.empty()){
					if(t == 0){
						int x = v.front();
						if((p[i][0] - p[x][0]) * 2 < T[i]) break;
						v.pop_front();
						if(T[x] > abs(p[i][0] - p[x][0]) * 2){
							T[x] = abs(p[i][0] - p[x][0]) * 2;
							qq.push({T[x], 1, x});
						}
					} if(t == 1){
						int x = v.back();
						if((p[x][0] - p[i][0]) * 2 < T[i]) break;
						v.pop_back();
						if(T[x] > abs(p[i][0] - p[x][0]) * 2){
							T[x] = abs(p[i][0] - p[x][0]) * 2;
							qq.push({T[x], 0, x});
						}
					} if(t == 2){
						int x = v.back();
						if((p[x][0] - p[i][0]) * 2 < T[i]) break;
						v.pop_back();
						if(T[x] > 2 * abs(p[i][0] - p[x][0])){
							T[x] = 2 * abs(p[i][0] - p[x][0]);
							qq.push({T[x], 3, x});
						}
					} if(t == 3){
						int x = v.front();
						if((p[i][0] - p[x][0]) * 2 < T[i]) break;
						v.pop_front();
						if(T[x] > 2 * abs(p[i][0] - p[x][0])){
							T[x] = 2 * abs(p[i][0] - p[x][0]);
							qq.push({T[x], 2, x});
						}
					}
				} swap(tmp, v);
			}
			
			{
				auto& v = m2[p[i][0] - p[i][1]];
				auto tmp = v;
				while(!v.empty()){
					if(t == 0){
						int x = v.back();
						if(2 * (p[x][0] - p[i][0]) < T[i]) break;
						v.pop_back();
						if(T[x] > 2 * abs(p[i][0] - p[x][0])){
							T[x] = 2 * abs(p[i][0] - p[x][0]);
							qq.push({T[x], 3, x});
						}
					} if(t == 1){
						int x = v.back();
						if(2 * (p[x][0] - p[i][0]) < T[i]) break;
						v.pop_back();
						if(T[x] > 2 * abs(p[i][0] - p[x][0])){
							T[x] = 2 * abs(p[i][0] - p[x][0]);
							qq.push({T[x], 2, x});
						}
					} if(t == 2){
						int x = v.front();
						if(2 * (p[i][0] - p[x][0]) < T[i]) break;
						v.pop_front();
						if(T[x] > 2 * abs(p[i][0] - p[x][0])){
							T[x] = 2 * abs(p[i][0] - p[x][0]);
							qq.push({T[x], 1, x});
						}
					} if(t == 3){
						int x = v.front();
						if(2 * (p[i][0] - p[x][0]) < T[i]) break;
						v.pop_front();
						if(T[x] > 2 * abs(p[i][0] - p[x][0])){
							T[x] = 2 * abs(p[i][0] - p[x][0]);
							qq.push({T[x], 0, x});
						}
					}
				} 
				swap(tmp, v);
			}
			
			if(t&1){
				auto& v = x[p[i][0]];
				for(auto x : v){
					if(t == 1 && T[i] <= p[x][0] - p[i][0] && T[x] > p[x][0] - p[i][0]){
						T[x] = p[x][0] - p[i][0];
						qq.push({T[x], 3, x});
					} if(t == 3 && T[i] <= p[i][0] - p[x][0] && T[x] > p[i][0] - p[x][0]){
						T[x] = p[i][0] - p[x][0];
						qq.push({T[x], 1, x});
					}
				}
			} else {
				auto& v = y[p[i][1]];
				for(auto x : v){
					if(t == 0 && T[i] <= p[x][1] - p[i][1] && T[x] > p[x][1] - p[i][1]){
						T[x] = p[x][1] - p[i][1];
						qq.push({T[x], 2, x});
					} if(t == 2 && T[i] <= p[i][1] - p[x][1] && T[x] > p[i][1] - p[x][1]){
						T[x] = p[i][1] - p[x][1];
						qq.push({T[x], 0, x});
					}
				}
			}
		}
		
		for(int i=0;i<n;i++){
			res += (T[i] < 1e18);
		}
		
		ans = max(ans, res);
		m1 = t1, m2 = t2;
	}
	
	cout<<ans<<"\n";
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:21:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto& [x, v] : m1){
      |            ^
fever.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  } for(auto& [x, v] : m2){
      |              ^
fever.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |  } for(auto& [x, v] : x){
      |              ^
fever.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  } for(auto& [x, v] : y){
      |              ^

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