Submission #430935

#TimeUsernameProblemLanguageResultExecution timeMemory
430935HideoIOI Fever (JOI21_fever)C++17
25 / 100
228 ms1848 KiB
#include <bits/stdc++.h> using namespace std; #define all(s) s.begin(), s.end() #define ll long long #define fr first #define sc second #define pb push_back #define mk make_pair #define pi pair < int, int > const int N = 3007; const int INF = 1e9 + 7; pi d[4] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; int x[N], y[N]; int us[N]; int n, ans; int check (int v, int u, int k, double t){ if (abs(x[v] - x[u]) != abs(y[v] - y[u])){ if (x[v] == x[u]){ if (t > abs(y[v] - y[u]) / 2.0) return -10; if (k == 2 && y[v] > y[u]) return -3; if (k == 3 && y[v] < y[u]) return -2; } else if (y[v] == y[u]){ if (t > abs(x[v] - x[u]) / 2.0) return -10; if (k == 1 && x[v] > x[u]) return -4; if (k == 0 && x[v] < x[u]) return -1; } return -10; } if (t > abs(x[v] - x[u])) return -10; if (k == 0){ if (x[u] < x[v]) return -10; if (y[u] > y[v]) return 2; else return 3; } if (k == 1){ if (x[u] > x[v]) return -10; if (y[u] > y[v]) return 2; else return 3; } if (k == 2){ if (y[u] > y[v]) return -10; if (x[u] > x[v]) return 1; else return 0; } if (k == 3){ if (y[u] < y[v]) return -10; if (x[u] > x[v]) return 1; else return 0; } } int solve (int ks){ int r = 0; priority_queue < pair < double, pi > > qr; qr.push({0, {ks, 1}}); while (!qr.empty()){ double t = -qr.top().fr; int k = qr.top().sc.fr, v = qr.top().sc.sc; qr.pop(); if (us[v]) continue; r++; us[v] = 1; for (int i = 2; i <= n; i++){ if (us[i]) continue; int nk = check(v, i, k, t); if (nk != -10){ if (nk < 0){ if (nk == -4) nk = 0; qr.push({-(abs(x[v] - x[i]) / 2.0), {-nk, i}}); } else qr.push({-abs(x[v] - x[i]), {nk, i}}); } } } return r; } main (){ cin >> n; for (int i = 1; i <= n; i++){ cin >> x[i] >> y[i]; } ans = max(ans, solve(0)); memset(us, 0, sizeof(us)); ans = max(ans, solve(1)); memset(us, 0, sizeof(us)); ans = max(ans, solve(2)); memset(us, 0, sizeof(us)); ans = max(ans, solve(3)); cout << ans; }

Compilation message (stderr)

fever.cpp:107:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  107 | main (){
      | ^~~~
fever.cpp: In function 'int check(int, int, int, double)':
fever.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
   75 | }
      | ^
#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...