| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 840023 |
2023-08-31T01:40:58 Z |
fanwen |
Džumbus (COCI19_dzumbus) |
C++17 |
|
57 ms |
12672 KB |
#include <bits/stdc++.h>
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
template <class A, class B> bool minimize(A &a, B b) { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b) { if (a < b) { a = b; return true; } return false; }
struct disjoint_set {
vector <int> lab;
disjoint_set () {}
disjoint_set (int n) : lab(n + 1, -1) {}
int find(int u) { return lab[u] < 0 ? u : lab[u] = find(lab[u]); }
bool merge(int u, int v) {
u = find(u); v = find(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
bool same_component (int u, int v) { return find(u) == find(v); }
int component_size(int i) { return -lab[find(i)]; }
};
const int MAXN = 1e3 + 5;
int N, M, Q, D[MAXN], sz[MAXN], vis[MAXN];
vector <int> adj[MAXN];
long long dp[MAXN][MAXN], F[MAXN];
void dfs(int u, int p) {
vis[u] = true;
sz[u] = 1;
dp[u][0] = 0, dp[u][1] = D[u];
for (auto v : adj[u]) if(v != p) {
dfs(v, u);
sz[u] += sz[v];
FOR(a, 2, sz[v]) minimize(dp[u][a], dp[v][a]);
FORD(b, sz[u], 1) {
FOR(a, 1, min(sz[v], b - 1)) {
minimize(dp[u][b], dp[v][a] + dp[u][b - a]);
}
}
}
}
void you_make_it(void) {
cin >> N >> M;
FOR(i, 1, N) cin >> D[i];
vector <pair <int, int>> edges(M);
for (auto &[u, v] : edges) cin >> u >> v;
sort(ALL(edges), [&](const pair <int, int> &a, const pair <int, int> &b) {
return D[a.first] + D[a.second] < D[b.first] + D[b.second];
});
disjoint_set dsu(N);
for (auto [u, v] : edges) {
if(dsu.merge(u, v)) {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
memset(dp, 0x3f, sizeof dp);
memset(F, 0x3f, sizeof F);
F[0] = 0;
FOR(i, 1, N) if(!vis[i]) {
dfs(i, 0);
FORD(j, N, 0) {
FOR(u, 2, min(sz[i], j)) {
minimize(F[j], F[j - u] + dp[i][u]);
}
}
}
vector <pair <int, int>> _F;
FOR(i, 0, N) {
_F.emplace_back(F[i], i);
}
sort(ALL(_F));
cin >> Q;
vector <pair <int, int>> queries(Q);
vector <int> ans(Q);
int Max = 0;
REP(i, Q) {
cin >> queries[i].first;
queries[i].second = i;
}
sort(ALL(queries));
int j = 0;
for (auto [u, i] : queries) {
while(j < N + 1 && _F[j].first <= u) maximize(Max, _F[j++].second);
ans[i] = Max - (Max == 1);
}
REP(i, Q) cout << ans[i] << '\n';
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
8396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
8396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
12672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
8396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
