Submission #1059025

#TimeUsernameProblemLanguageResultExecution timeMemory
1059025qwushaFountain Parks (IOI21_parks)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second typedef long double ld; const ld eps = 1e-8; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); const ll inf = 1e18; const ll mod = 1e9 + 7; #include "parks.h" vector<vector<int>> g; vector<int> u, v, a, b; vector<int> used; void dfs(int ver) { used[ver] = 1; for (auto nod : g[ver]) { if (!used[nod]) { u.push_back(ver); v.push_back(nod); dfs(nod); } } } int construct_roads(vector<int> x, vector<int> y) { bool fir = 1, sec = 1, thi = 1; int n = x.size(); for (int i = 0; i < n; i++) { if (x[i] != 2) fir = 0; } map<pair<int, int>, int> mp; for (int i = 0; i < n; i++) { mp[{x[i], y[i]}] = i; } g.resize(n); for (int i = 0; i < n; i++) { if (mp.find({x[i] - 2, y[i]}) != mp.end()) { g[i].push_back(mp[{x[i] - 2, y[i]}]); } if (mp.find({x[i] + 2, y[i]}) != mp.end()) { g[i].push_back(mp[{x[i] + 2, y[i]}]); } if (mp.find({x[i], y[i] - 2}) != mp.end()) { g[i].push_back(mp[{x[i], y[i] - 2}]); } if (mp.find({x[i], y[i] + 2}) != mp.end()) { g[i].push_back(mp[{x[i], y[i] + 2}]); } } used.resize(n); dfs(0); bool ch = 1; for (int i = 0; i < n; i++) { if (!used[i]) ch = 0; } if (!ch) return 0; map<pair<int, int>, int> bench; map<pair<int, int>, set<int>> want; set<vector<int>> ben; for (int i = 0; i < v.size(); i++) { if (x[v[i]] == x[u[i]]) { want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].insert(i); want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].insert(i); bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]++; bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]++; } else { want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].insert(i); want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].insert(i); bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]++; bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]++; } } for (auto [pa, cnt] : bench) { ben.insert({cnt, pa.fi, pa.se}); } a.resize(n - 1); b.resize(n - 1); while(!ben.empty()) { auto cur = *ben.begin(); int i = *want[{cur[1], cur[2]}].begin(); if (cur[0] > 1) while(1) a[i] = cur[1]; b[i] = cur[2]; if (x[v[i]] == x[u[i]]) { want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].erase(i); want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].erase(i); ben.erase({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2}); ben.erase({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}); bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]--; bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]--; if (bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}] > 0) { ben.insert({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2}); } if (bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}] > 0) { ben.insert({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}); } } else { want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].erase(i); want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].erase(i); ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 }); ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}); bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]--; bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]--; if ( bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}] > 0) { ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 }); } if (bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}] > 0) { ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}); } } } build(u, v, a, b); return 1; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
parks.cpp:34:10: warning: variable 'fir' set but not used [-Wunused-but-set-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |          ^~~
parks.cpp:34:19: warning: unused variable 'sec' [-Wunused-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |                   ^~~
parks.cpp:34:28: warning: unused variable 'thi' [-Wunused-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |                            ^~~
#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...