Submission #826269

#TimeUsernameProblemLanguageResultExecution timeMemory
826269loctildoreFountain Parks (IOI21_parks)C++17
70 / 100
1285 ms69520 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; // trans rights #define ll long long #define f first #define s second #define endl '\n' #define all(x) begin(x), end(x) int n; vector<int> u, v, a, b; map<pair<int, int>, int> mp; set<pair<int, int>> done; vector<pair<int, int>> dirs = {{0, 2}, {2, 0}, {0, -2}, {-2, 0}}; vector<pair<int, int>> bloc[2] = {{{-1, 1}, {1, 1}, {1, -1}, {-1, -1}}, {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}}}; void dfs(int x, int y, int ldir = 0) { done.insert({x, y}); for (int i = 0; i < 4; i++) { int ndir = (ldir + 3 + i) % 4; int nx = x + dirs[ndir].f; int ny = y + dirs[ndir].s; if (mp.find({nx, ny}) == mp.end()) continue; if (done.find({nx, ny}) != done.end()) continue; int tx = x + bloc[0][ndir].f; int ty = y + bloc[0][ndir].s; if (done.find({tx, ty}) == done.end()) { u.push_back(mp[{x, y}]); v.push_back(mp[{nx, ny}]); done.insert({tx, ty}); a.push_back(tx); b.push_back(ty); dfs(nx, ny, ndir); continue; } tx = x + bloc[1][ndir].f; ty = y + bloc[1][ndir].s; if (done.find({tx, ty}) == done.end()) { u.push_back(mp[{x, y}]); v.push_back(mp[{nx, ny}]); done.insert({tx, ty}); a.push_back(tx); b.push_back(ty); dfs(nx, ny, ndir); } } } int construct_roads(vector<int> xs, vector<int> ys) { srand(69); n = xs.size(); for (int i = 0; i < n; i++) { mp[{xs[i], ys[i]}] = i; } int nxt = 0; for (int tst = 0; tst < 7; tst++) { dfs(xs[nxt], ys[nxt]); if (u.size() == n - 1) { build(u, v, a, b); return 1; } for (int i = 0; i < n; i++) { if (done.find({xs[i], ys[i]}) == done.end()) nxt = i; } done.clear(); u.clear(); v.clear(); a.clear(); b.clear(); } return 0; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if (u.size() == n - 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...