Submission #617807

#TimeUsernameProblemLanguageResultExecution timeMemory
617807amunduzbaevFountain Parks (IOI21_parks)C++17
5 / 100
841 ms49816 KiB
#include "parks.h" #include "bits/stdc++.h" using namespace std; #ifndef EVAL #include "grader.cpp" #endif #define ar array typedef long long ll; const int N = 2e5 + 5; vector<ar<int, 3>> edges[N]; int construct_roads(vector<int> x, vector<int> y) { int n = x.size(); map<ar<int, 2>, int> ss, mm; for(int i=0;i<n;i++){ ss[{x[i], y[i]}] = i; } vector<ar<int, 2>> e, p; auto add = [&](int a, int b, int p1, int p2){ edges[a].push_back({b, p1, p2}); edges[b].push_back({a, p1, p2}); }; for(int i=0;i<n;i++){ if(ss.count({x[i] - 2, y[i]})){ int j = ss[{x[i] - 2, y[i]}]; e.push_back({i, j}); p.push_back({-1, -1}); int u = e.size() - 1; if(mm.count({x[i] - 1, y[i] - 1})){ int v = mm[{x[i] - 1, y[i] - 1}]; add(u, v, x[i] - 1, y[i] - 1); mm.erase({x[i] - 1, y[i] - 1}); } else { mm[{x[i] - 1, y[i] - 1}] = u; } if(mm.count({x[i] - 1, y[i] + 1})){ int v = mm[{x[i] - 1, y[i] + 1}]; add(u, v, x[i] - 1, y[i] + 1); mm.erase({x[i] - 1, y[i] + 1}); } else { mm[{x[i] - 1, y[i] + 1}] = u; } } if(ss.count({x[i], y[i] - 2})){ int j = ss[{x[i], y[i] - 2}]; e.push_back({i, j}); p.push_back({-1, -1}); int u = e.size() - 1; if(mm.count({x[i] - 1, y[i] - 1})){ int v = mm[{x[i] - 1, y[i] - 1}]; add(u, v, x[i] - 1, y[i] - 1); mm.erase({x[i] - 1, y[i] - 1}); } else { mm[{x[i] - 1, y[i] - 1}] = u; } if(mm.count({x[i] + 1, y[i] - 1})){ int v = mm[{x[i] + 1, y[i] - 1}]; add(u, v, x[i] + 1, y[i] - 1); mm.erase({x[i] + 1, y[i] - 1}); } else { mm[{x[i] + 1, y[i] - 1}] = u; } } } int m = e.size(); if(m != n - 1) return 0; assert(m == n - 1); for(int i=0;i<m;i++){ assert((int)edges[i].size() <= 2); } for(auto [x, i] : mm){ p[i] = x; assert((int)edges[i].size() < 2); } vector<int> used(m); function<void(int)> dfs = [&](int i){ used[i] = 1; for(auto [x, p1, p2] : edges[i]){ if(used[x]) continue; p[x] = {p1, p2}; dfs(x); } }; for(int i=0;i<m;i++){ if(used[i]) continue; if(p[i][0] == -1){ assert(edges[i].size() == 2); p[i] = {edges[i].back()[1], edges[i].back()[2]}; edges[i].pop_back(); } dfs(i); } vector<int> u(m), v(m), A(m), B(m); for(int i=0;i<m;i++){ u[i] = e[i][0], v[i] = e[i][1]; A[i] = p[i][0], B[i] = p[i][1]; assert(~A[i] && ~B[i]); } build(u, v, A, B); return 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...