Submission #812704

#TimeUsernameProblemLanguageResultExecution timeMemory
812704piOOEGarden (JOI23_garden)C++17
0 / 100
53 ms436 KiB
#include <bits/stdc++.h> using namespace std; struct Cycle { vector<bool> a; vector<int> nxt, prv; int n = 0, mx = 0; Cycle(int n) : n(n), mx(0), a(n, 0), nxt(n), prv(n) {} void ins(int i) { assert(!a[i]); a[i] = true; int l = i == 0 ? n - 1 : i - 1, r = i + 1 == n ? 0 : i + 1; prv[i] = a[l] ? prv[l] : i, nxt[i] = a[r] ? nxt[r] : i; mx = max(mx, (nxt[i] - prv[i] + n) % n + 1); } int query() { return mx; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, d; cin >> n >> m >> d; vector<int> needx(2 * d), needy(2 * d); vector<vector<int>> points(2 * d); for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; needx[a] = needy[b] = true; } for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; if (needx[a] || needy[b]) { continue; } points[a].push_back(b); } for (int i = 0; i < d; ++i) { needx[i + d] = needx[i]; needy[i + d] = needy[i]; points[i + d] = points[i]; } int ans = d * d; vector<vector<int>> lastVec(d); for (int L = 1; L <= d; ++L) { if (!needx[L - 1]) { continue; } int R = L; while (!needx[R]) { R += 1; } vector<int> last(d, -1); for (int l = R - 1; l >= L; --l) { for (int y : points[l]) { last[y] = l; } for (int i = l; i < R; ++i) { lastVec[i].clear(); } Cycle c(d); for (int y = 0; y < d; ++y) { if (needy[y]) { continue; } if (last[y] == -1) { c.ins(y); } else { lastVec[last[y]].push_back(y); } } for (int r = R; r >= l; --r) { if (r + 1 < R) { for (int y : lastVec[r]) { c.ins(y); } } ans = min(ans, (d - (r - l)) * (d - c.query())); } } } cout << ans << '\n'; return 0; }

Compilation message (stderr)

garden.cpp: In constructor 'Cycle::Cycle(int)':
garden.cpp:8:16: warning: 'Cycle::mx' will be initialized after [-Wreorder]
    8 |     int n = 0, mx = 0;
      |                ^~
garden.cpp:6:18: warning:   'std::vector<bool> Cycle::a' [-Wreorder]
    6 |     vector<bool> a;
      |                  ^
garden.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     Cycle(int n) : n(n), mx(0), a(n, 0), nxt(n), prv(n) {}
      |     ^~~~~
#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...