Submission #973939

#TimeUsernameProblemLanguageResultExecution timeMemory
973939alextodoranIOI Fever (JOI21_fever)C++17
19 / 100
1 ms604 KiB
/** _ _ __ _ _ _ _ _ _ |a ||t ||o d | |o | | __ _| | _ | __| _ | | __ |/_ | __ /__\ / _\| **/ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N_MAX = 100000; const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3; int N; int X[N_MAX + 2], Y[N_MAX + 2]; int order[N_MAX + 2]; unordered_map <int, deque <int>> D1, D2; int dir[N_MAX + 2]; int min_len[N_MAX + 2]; bool seen[N_MAX + 2]; priority_queue <pair <int, int>> q; /* 1\ 0 /0 \|/ 1-x-3 /|\ 2/ 2 \3 */ void go (int i) { if (dir[i] == UP || dir[i] == RIGHT) { int d = X[i] - Y[i]; while (D1[d].empty() == false) { int j = D1[d].back(); if (seen[j] == true) { D1[d].pop_back(); } else if (min_len[i] <= X[j] - X[i] && X[j] - X[i] < min_len[j]) { D1[d].pop_back(); min_len[j] = X[j] - X[i]; q.push({-min_len[j], j}); } else { break; } } } if (dir[i] == LEFT || dir[i] == UP) { int d = X[i] + Y[i]; while (D2[d].empty() == false) { int j = D2[d].front(); if (seen[j] == true) { D2[d].pop_front(); } else if (min_len[i] <= X[i] - X[j] && X[i] - X[j] < min_len[j]) { D2[d].pop_front(); min_len[j] = X[i] - X[j]; q.push({-min_len[j], j}); } else { break; } } } if (dir[i] == DOWN || dir[i] == LEFT) { int d = X[i] - Y[i]; while (D1[d].empty() == false) { int j = D1[d].front(); if (seen[j] == true) { D1[d].pop_front(); } else if (min_len[i] <= X[i] - X[j] && X[i] - X[j] < min_len[j]) { D1[d].pop_front(); min_len[j] = X[i] - X[j]; q.push({-min_len[j], j}); } else { break; } } } if (dir[i] == RIGHT || dir[i] == DOWN) { int d = X[i] + Y[i]; while (D2[d].empty() == false) { int j = D2[d].back(); if (seen[j] == true) { D2[d].pop_back(); } else if (min_len[i] <= X[j] - X[i] && X[j] - X[i] < min_len[j]) { D2[d].pop_back(); min_len[j] = X[j] - X[i]; q.push({-min_len[j], j}); } else { break; } } } } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; for (int i = 1; i <= N; i++) { cin >> X[i] >> Y[i]; } iota(order + 1, order + N + 1, 1); sort(order + 1, order + N + 1, [&] (const int &i, const int &j) { return X[i] < X[j]; }); int answer = 0; for (int d1 : {UP, LEFT, DOWN, RIGHT}) { for (int k = 1; k <= N; k++) { int i = order[k]; D1[X[i] - Y[i]].push_back(i); D2[X[i] + Y[i]].push_back(i); } dir[1] = d1; for (int i = 2; i <= N; i++) { if (abs(X[i] - X[1]) > abs(Y[i] - Y[1])) { dir[i] = (X[i] < X[1] ? RIGHT : LEFT); } else if (abs(Y[i] - Y[1]) > abs(X[i] - X[1])) { dir[i] = (Y[i] < Y[1] ? UP : DOWN); } else { if (d1 == UP) { if (Y[i] < Y[1]) { dir[i] = UP; } else { dir[i] = (X[i] < X[1] ? RIGHT : LEFT); } } if (d1 == LEFT) { if (X[i] > X[1]) { dir[i] = LEFT; } else { dir[i] = (Y[i] < Y[1] ? UP : DOWN); } } if (d1 == DOWN) { if (Y[i] > Y[1]) { dir[i] = DOWN; } else { dir[i] = (X[i] < X[1] ? RIGHT : LEFT); } } if (d1 == RIGHT) { if (X[i] < X[1]) { dir[i] = RIGHT; } else { dir[i] = (Y[i] < Y[1] ? UP : DOWN); } } } } fill(min_len + 1, min_len + N + 1, INT_MAX); fill(seen + 1, seen + N + 1, false); min_len[1] = 0; q.push({0, 1}); int cnt = 0; while (q.empty() == false) { int i = q.top().second; q.pop(); if (seen[i] == true) { continue; } seen[i] = true; cnt++; go(i); } answer = max(answer, cnt); D1.clear(); D2.clear(); } cout << answer << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...