# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
428555 | 2021-06-15T12:51:24 Z | pavement | Park (JOI17_park) | C++17 | 0 ms | 0 KB |
#include "park.h" #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back static int Place[1405], link[1405], sz[1405]; int find(int x) { if (x == link[x]) return x; return link[x] = find(link[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[b] > sz[a]) swap(a, b); sz[a] += sz[b]; link[b] = a; } void solve(int l, int r) { if (find(l) == find(r)) return; int lo = 0, hi = N - 1, ans = -1; while (lo <= hi) { int mid = (lo + hi) / 2; memset(Place, 0, sizeof Place); for (int i = 0; i <= mid; i++) Place[i] = 1; Place[l] = Place[r] = 1; if (l >= r ? Ask(r, l, Place) : Ask(l, r, Place)) ans = mid, hi = mid - 1; else lo = mid + 1; } if (ans == 0) { l >= r ? Answer(r, l) : Answer(l, r); unite(l, r); } else { solve(l, ans); solve(ans, r); } }