제출 #699636

#제출 시각아이디문제언어결과실행 시간메모리
699636nayhzPark (BOI16_park)C++17
100 / 100
1016 ms90596 KiB
// source identifier task_name #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #define lck cout << "ick bmi 32.9\n" #define cam_cs cout << "ick orz\n" #define orz(x) cout << (x) << " orz\n" #define pii pair<int, int> #define pll pair<long long, long long> #define pcc pair<char, char> #define ll long long #define ull unsignedge long long #define ld long double #define int long long #define vi vector<int> #define vll vector<long long> #define vd vector<double> #define vpii vector<pair<int, int>> #define vpll vector<pair<long long, long long>> #define vc vector<char> #define vsc vector<string> #define vb vector<bool> #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define yes() cout << "Yes\n" #define no() cout << "No\n" #define impossible() cout << "Impossible\n" template<typename T, typename V> inline void print (const std::pair<T, V> &x) {std::cout << x.first << ' ' << x.second << '\n';} template<typename T> inline void print (const T &x) {std::cout << x << '\n';} template<typename T> inline void print (std::vector<T> &x) {for (auto &y : x) std::cout << y << " "; std::cout << '\n';} inline void print () {std::cout << '\n';} template<typename... T> inline void print(T&&... args) {((std::cout << args << " "), ...);std::cout << '\n';} using namespace std; const ld pi = acos(-1); const ld eps = 1e-9; const ll mod = 1000000007; const ll inf = 1000000007; clock_t T, NT; inline double get_time() {NT = clock() - T; return (double)(NT) / CLOCKS_PER_SEC;} void file_io (string x); /* >>>>>>>>>>>>>>>>>>>>>>>>>>END OF TEMPLATE HEADER<<<<<<<<<<<<<<<<<<<<<<<< */ template<int SZ> struct DSU { int parent[SZ], sz[SZ]; void init () { for (int i = 0; i < SZ; i++) parent[i] = i, sz[i] = 1; } int find (int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void merge (int u, int v) { int a = find(u), b = find(v); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); parent[b] = a; sz[a] += sz[b]; } }; DSU<2005> dsu; void solve (/*int &tc*/) { int n, m, w, h; cin >> n >> m >> w >> h; vector<pair<pii, int>> trees(n); set<pii> pts; vector<pair<int, pair<pii, pii>>> edge; map<pii, int> cc; auto dist = [&] (int x1, int y1, int x2, int y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }; auto add = [&] (int x1, int y1, int x2, int y2, int r1, int r2) { int ndist = dist(x1, y1, x2, y2) - r1 - r2; edge.pb({ndist, {{x1, y1}, {x2, y2}}}); }; for (int i = 0; i < n; i++) { cin >> trees[i].fi.fi >> trees[i].fi.se >> trees[i].se; pts.insert({trees[i].fi.fi, trees[i].fi.se}); cc[{0, trees[i].fi.se}] = 3; cc[{trees[i].fi.fi, h}] = 2; cc[{w, trees[i].fi.se}] = 1; cc[{trees[i].fi.fi, 0}] = 0; add(trees[i].fi.fi, trees[i].fi.se, 0, trees[i].fi.se, trees[i].se, 0); add(trees[i].fi.fi, trees[i].fi.se, trees[i].fi.fi, 0, trees[i].se, 0); add(trees[i].fi.fi, trees[i].fi.se, w, trees[i].fi.se, trees[i].se, 0); add(trees[i].fi.fi, trees[i].fi.se, trees[i].fi.fi, h, trees[i].se, 0); } int cnt = 4; for (auto &x : pts) cc[x] = cnt++; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) add(trees[i].fi.fi, trees[i].fi.se, trees[j].fi.fi, trees[j].fi.se, trees[i].se, trees[j].se); vector<pair<pii, int>> queries; for (int i = 0; i < m; i++) { int r, e; cin >> r >> e; e--; queries.pb({{(r << 1), e}, i}); } sort(all(queries)); sort(all(edge)); dsu.init(); int pt = 0; vector<vb> ok(m + 5, vb(4, true)); for (auto e : edge) { while (pt < (int)queries.size() && queries[pt].fi.fi <= e.fi) { bool conn[4][4]; pair<pii, int> curr = queries[pt]; for (int i = 0; i < 4; i++) { conn[i][i] = true; for (int j = i + 1; j < 4; j++) conn[i][j] = conn[j][i] = (dsu.find(i) == dsu.find(j)); } function<bool(int)> bad = [&] (int x) { return conn[(x - 1 < 0 ? 3 : x - 1)][x]; }; for (int i = 0; i < 4; i++) { if (curr.fi.se == i) continue; if (bad(curr.fi.se) || bad(i)) { ok[curr.se][i] = false; continue; } bool up = conn[0][2]; bool side = conn[1][3]; if (abs(curr.fi.se - i) == 2) { if (up || side) { ok[curr.se][i] = false; continue; } } else if (curr.fi.se + i == 3) { if (side) { ok[curr.se][i] = false; continue; } } else if (up) { ok[curr.se][i] = false; } } pt++; if (pt >= (int)queries.size()) break; } dsu.merge(cc[e.se.fi], cc[e.se.se]); } for (int i = 0; i < m; i++) { string ans = ""; for (int j = 0; j < 4; j++) if (ok[i][j]) ans.pb((char)(j + '1')); cout << ans << '\n'; } } signed main () { cin.tie(0)->sync_with_stdio(false); T = clock(); srand(time(NULL)); // file_io(""); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { solve(/*i*/); // if (i != t) cout << '\n'; } // while (true) {solve(t); t++;} return 0; } // void file_io (string x = "x") { // string i = x + ".in"; // freopen(i.c_str(), "r", stdin); // string o = x + ".out"; // freopen(o.c_str(), "w", stdout); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...