Submission #935018

#TimeUsernameProblemLanguageResultExecution timeMemory
935018mostafa133Odašiljači (COCI20_odasiljaci)C++14
0 / 70
105 ms728 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; typedef long double ld; using namespace std; using namespace __gnu_pbds; using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>; #define all(x) x.begin(), x.end() #define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) void dfs(ll cur, vector<bool> &vis, vector<pair<ll, ll>> &v, ld md) { if (vis[cur]) { return; } vis[cur] = 1; for (int i = 0; i < vis.size(); i++) { if (vis[i]) continue; ll x = abs(v[i].first - v[cur].first), y = abs(v[i].second - v[cur].second); ll dis = x * x + y * y; if (sqrt(dis) > md) { // cout << md << ' ' << md * md; continue; } dfs(i, vis, v, md); } // if ((v[cur].second) > md * md) { // cout << md << ' ' << md * md; // return; } } int main() { fast; // freopen("pails.in", "r", stdin); // freopen("pails.out", "w", stdout); ll n; cin >> n; vector<pair<ll, ll>> v(n); for (int i = 0; i < n; i++) { cin >> v[i].first >> v[i].second; } // ll mx = 0; vector<pair<ll, ll>> close(n); for (int i = 0; i < n; i++) { ll mn = LLONG_MAX, mnin = 0; for (int j = 0; j < n; j++) { if (j == i) { continue; } ll x = abs(v[i].first - v[j].first), y = abs(v[i].second - v[j].second); ll dis = x * x + y * y; if (dis < mn) { mn = dis, mnin = j; } } close[i] = {mnin, mn}; } for (int i = 0; i < n; i++) { cout << i << ": " << close[i].first << ' ' << close[i].second << '\n'; } ld l = 0, r = 1e9; vector<bool> vis; while (l <= r) { ld md = (l + r) / 2; vis = vector<bool>(n, 0); dfs(0, vis, v, md); for (int i = 0; i < n; i++) { cout << vis[i]; } if (md < 2) { for (int i = 0; i < n; i++) { cout << md; } cout << '\n'; } cout << '\n'; if (find(all(vis), 0) == vis.end()) { // cout << 1; r = md - 1e-7; } else { l = md + 1e-7; } } // cout << '\n'; cout << fixed << setprecision(10) << l / 2; return 0; }

Compilation message (stderr)

odasiljaci.cpp: In function 'void dfs(ll, std::vector<bool>&, std::vector<std::pair<long long int, long long int> >&, ld)':
odasiljaci.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < vis.size(); i++)
      |                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...