Submission #653396

#TimeUsernameProblemLanguageResultExecution timeMemory
653396leeh18Džumbus (COCI19_dzumbus)C++17
110 / 110
56 ms23268 KiB
#include <bits/stdc++.h> #include <algorithm> #include <cassert> #include <vector> namespace atcoder { struct dsu { public: dsu() : _n(0) {} explicit dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } private: int _n; std::vector<int> parent_or_size; }; } // namespace atcoder using namespace std; constexpr auto inf = numeric_limits<long long>::max() / 2; auto operator+(const vector<long long> &a, const vector<long long> &b) { assert(a.size() == b.size()); vector<long long> c(a.size()); for (auto i = 0U; i < a.size(); ++i) { c[i] = min(a[i], b[i]); } return c; } auto operator*(const vector<long long> &a, const vector<long long> &b) { vector<long long> c(a.size() + b.size() - 1U, inf); for (auto i = 0U; i < a.size(); ++i) { for (auto j = 0U; j < b.size(); ++j) { c[i + j] = min(c[i + j], a[i] + b[j]); } } return c; } int main() { cin.tie(0)->sync_with_stdio(0); int N, M; cin >> N >> M; vector<long long> D(N + 1); copy_n(istream_iterator<long long>(cin), N, next(D.begin())); vector<vector<int>> adj(N + 1); atcoder::dsu dsu(N + 1); for (auto i = 0; i < M; ++i) { int A, B; cin >> A >> B; adj[A].push_back(B); adj[B].push_back(A); dsu.merge(A, B); } for (auto i = 1; i <= N; ++i) { if (dsu.leader(i) == i) { adj[0].push_back(i); } } vector<vector<vector<long long>>> dp(3, vector<vector<long long>>(N + 1)); auto f = [&](auto self, int u, int p) -> void { dp[0][u] = {inf, inf}; dp[1][u] = {inf, D[u]}; dp[2][u] = {0LL, inf}; for (auto v : adj[u]) if (v != p) { self(self, v, u); dp[0][u] = dp[0][u] * (dp[0][v] + dp[1][v] + dp[2][v]) + dp[1][u] * (dp[0][v] + dp[1][v]); dp[1][u] = dp[1][u] * dp[2][v]; dp[2][u] = dp[2][u] * (dp[0][v] + dp[2][v]); } }; f(f, 0, 0); auto v = dp[2][0]; int Q; cin >> Q; vector<pair<long long, int>> qs; qs.reserve(Q); for (auto i = 0; i < Q; ++i) { long long S; cin >> S; qs.emplace_back(S, i); } vector<int> ans(Q); sort(qs.rbegin(), qs.rend()); for (auto [S, i] : qs) { while (v.back() > S) { v.pop_back(); } ans[i] = static_cast<int>(v.size()) - 1; } copy(ans.begin(), ans.end(), ostream_iterator<int>(cout, "\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...