Submission #521411

#	Time	Username	Problem	Language	Result	Execution time	Memory
521411		amunduzbaev	IOI Fever (JOI21_fever)	C++14	0 / 100	1 ms	204 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, vector<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]].pu
	}
	
	for(auto& [x, v] : m1){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
		//~ for(int i=0;i<(int)v.size();i++) p1[v[i]] = i;
	}
	
	for(auto& [x, v] : m2){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
		//~ for(int i=0;i<(int)v.size();i++) p2[v[i]] = i;
	}
	
	int ans = 0;
	for(int t=0;t<4;t++){
		vector<int> used(n);
		used[0] = 1;
		queue<ar<int, 2>> qq; qq.push({0, t});
		set<int> u1, u2;
		int res = 0;
		while(!qq.empty()){
			res++;
			auto u = qq.front(); qq.pop();
			int i = u[0], t = u[1];
			if(!u1.count(p[i][0] + p[i][1])){
				auto& v = m1[p[i][0] + p[i][1]];
				if(v.back() == i && (t == 1 || t == 2));
				else if(v[0] == i && (t == 0 || t == 3));
				else {
					int tt = (t < 2 ? 1 : 2);
					for(auto x : v){
						if(x == i) tt = (t < 2 ? 0 : 3);
						if(used[x]) continue;
						used[x] = 1;
						qq.push({x, tt});
					}
					u1.insert(p[i][0] + p[i][1]);
				}
			}
			
			if(!u2.count(p[i][0] - p[i][1])){
				auto& v = m2[p[i][0] - p[i][1]];
				if(v.back() == i && (t == 0 || t == 1));
				else if(v[0] == i && (t == 2 || t == 3));
				else {
					int tt = (t == 0 || t == 3 ? 0 : 1);
					for(auto x : v){
						if(x == i) tt = (tt == 0 ? 3 : 2);
						if(used[x]) continue;
						used[x] = 1;
						qq.push({x, tt});
					}
					u2.insert(p[i][0] - p[i][1]);
				}
			}
		}
		
		ans = max(ans, res);
	}
	
	cout<<ans<<"\n";
}

Compilation message (stderr)

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

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