Submission #1226942

#TimeUsernameProblemLanguageResultExecution timeMemory
1226942dksnfjkfnwkfwDžumbus (COCI19_dzumbus)C++20
0 / 110
115 ms1144 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1005; int n, m, q; int need[N]; vector<int> adj[N]; vector<int> path, pre; void dfs(int u, int p) { path.push_back(u); for (int v : adj[u]) { if (v != p) dfs(v, u); } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> need[i]; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int start = 1; for (int i = 1; i <= n; ++i) { if (adj[i].size() == 1) { start = i; break; } } dfs(start, -1); int sz = path.size(); pre.resize(sz + 1); for (int i = 1; i <= sz; ++i) pre[i] = pre[i - 1] + need[path[i - 1]]; cin >> q; while (q--) { int D; cin >> D; int ans = 0; for (int i = 1; i <= sz; ++i) { int l = i, r = sz, best = i - 1; while (l <= r) { int mid = (l + r) / 2; int sum = pre[mid] - pre[i - 1]; if (sum <= D) { best = mid; l = mid + 1; } else { r = mid - 1; } } int len = best - i + 1; if (len >= 2) ans = max(ans, len); } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...