| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 699183 |
2023-02-16T00:51:04 Z |
badont |
Džumbus (COCI19_dzumbus) |
C++17 |
|
50 ms |
11444 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
#define FOR(i,n) for (int i = 1; i <= n; i++)
#define F0R(i,n) for (int i = 0; i < n; i++)
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
using ll = long long;
using ld = long double;
struct DSU {
ll mxn;
vector<ll> par, sz;
DSU(ll ini){
mxn = ini;
par.assign(ini + 5, 0);
sz.assign(ini + 5, 1);
FOR(i, mxn) par[i] = i;
}
ll fnd(ll g){
if(g == par[g]) return g;
return par[g] = fnd(par[g]);
}
void uni(ll a, ll b){
a = fnd(a), b = fnd(b);
if(a == b) return;
if(sz[a] <= sz[b]) swap(a, b); // a bigger
par[b] = a; sz[a] += sz[b];
}
};
const ll INF = 1e18;
void solve() {
ll n, m;
cin >> n >> m;
n++;
vector<ll> D(n);
D[0] = INF;
FOR (i, n - 1) cin >> D[i];
vector e(n, vector<ll>());
DSU dsu(n - 1);
while (m--) {
ll x, y;
cin >> x >> y;
dsu.uni(x, y);
e[x].pb(y);
e[y].pb(x);
}
vector<ll> vis(n);
FOR (i, n - 1) if (!vis[dsu.fnd(i)]) {
vis[dsu.fnd(i)] = true;
e[0].pb(dsu.fnd(i));
e[dsu.fnd(i)].pb(0);
}
vector dp(2, vector(n, vector<ll>()));
vector<ll> sub(n);
auto dfs = [&](auto dfs, ll g, ll p) -> void {
sub[g] = 1;
for (auto u : e[g]) if (u != p) {
dfs(dfs, u, g);
sub[g] += sub[u];
}
auto& dp0 = dp[0][g], &dp1 = dp[1][g];
dp0.resize(2);
dp1.resize(2);
//dp0 force non inclusion
//dp1 force inclusion
dp0[0] = 0; dp1[0] = INF;
dp0[1] = INF; dp1[1] = INF;
ll c_size = 1;
for (auto& u : e[g]) if (u != p) {
auto& cp0 = dp[0][u];
auto& cp1 = dp[1][u];
c_size += sub[u];
//debug(c_size);
vector<ll> ndp0(c_size + 1, INF), ndp1(c_size + 1, INF);
for (int i = 0; i < (int)dp0.size(); i++) {
for (int j = 0; j < (int)cp0.size(); j++) if (dp0[i] < INF and cp0[j] < INF) {
assert(i + j < (int)ndp0.size());
ndp0[i + j] = min(ndp0[i + j], dp0[i] + cp0[j]);
}
for (int j = 0; j < (int)cp1.size(); j++) if (dp0[i] < INF and cp1[j] < INF) {
//debug(u, g, i, j, dp0[i], cp1[j]);
assert(i + j < (int)ndp0.size());
ndp0[i + j] = min(ndp0[i + j], dp0[i] + cp1[j]);
}
}
debug(u, g, "here");
for (int i = 0; i < (int)dp0.size(); i++) {
for (int j = 0; j < (int)cp0.size(); j++) if (dp0[i] < INF and cp0[j] < INF and D[g] < INF and D[u] < INF){
assert(i + j + 2 < (int)ndp1.size());
ndp1[i + j + 2] = min(ndp1[i + j + 2], dp0[i] + cp0[j] + D[g] + D[u]);
}
for (int j = 0; j < (int)cp1.size(); j++) if (dp0[i] < INF and cp1[j] < INF and D[g] < INF){
ndp1[i + j + 1] = min(ndp1[i + j + 1], dp0[i] + cp1[j] + D[g]);
}
}
for (int i = 0; i < (int)dp1.size(); i++) {
for (int j = 0; j < (int)cp0.size(); j++) if (dp1[i] != INF and cp0[j] != INF) {
assert(i + j + 1 < (int)ndp1.size());
ndp1[i + j] = min(ndp1[i + j], dp1[i] + cp0[j]);
if (D[u] < INF) ndp1[i + j + 1] = min(ndp1[i + j + 1], dp1[i] + cp0[j] + D[u]);
}
for (int j = 0; j < (int)cp1.size(); j++) if (dp1[i] != INF and cp1[j] != INF) {
assert(i + j < (int)ndp1.size());
ndp1[i + j] = min(ndp1[i + j], dp1[i] + cp1[j]);
}
}
swap(ndp0, dp0);
swap(ndp1, dp1);
ndp0.clear();
ndp1.clear();
}
debug(g, dp0, dp1);
};
dfs(dfs, 0, -1);
ll q; cin >> q;
vector<ll> rets;
for (int i = 2; i <= n; i++)
rets.pb(i);
sort(all(rets), [&](ll x, ll y){
return dp[0][0][x] < dp[0][0][y];
});
vector<ll> p = rets;
for (int i = 1; i < (int)p.size(); i++) {
p[i] = max(p[i], p[i - 1]);
}
while (q--) {
ll x; cin >> x;
auto& ref = dp[0][0];
assert(ref[0] == 0 and ref.size() == n + 1);
ll lo = 0, hi = (int)p.size() - 1, mid;
while (lo < hi) {
mid = (lo + hi + 1) >> 1;
if (ref[rets[mid]] <= x) lo = mid;
else hi = mid - 1;
}
cout << (hi == lo and ref[rets[lo]] <= x ? p[lo] : 0) << '\n';
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
solve();
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from dzumbus.cpp:4:
dzumbus.cpp: In function 'void solve()':
dzumbus.cpp:181:43: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
181 | assert(ref[0] == 0 and ref.size() == n + 1);
| ~~~~~~~~~~~^~~~~~~~
dzumbus.cpp: In instantiation of 'solve()::<lambda(auto:1, ll, ll)> [with auto:1 = solve()::<lambda(auto:1, ll, ll)>; ll = long long int]':
dzumbus.cpp:162:19: required from here
dzumbus.cpp:26:20: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) "zzz"
| ^~~~~
dzumbus.cpp:129:13: note: in expansion of macro 'debug'
129 | debug(u, g, "here");
| ^~~~~
dzumbus.cpp:26:20: warning: statement has no effect [-Wunused-value]
26 | #define debug(...) "zzz"
| ^~~~~
dzumbus.cpp:159:9: note: in expansion of macro 'debug'
159 | debug(g, dp0, dp1);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8588 KB |
Output is correct |
| 3 |
Correct |
45 ms |
10700 KB |
Output is correct |
| 4 |
Correct |
48 ms |
11444 KB |
Output is correct |
| 5 |
Correct |
50 ms |
10976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 2 |
Correct |
29 ms |
920 KB |
Output is correct |
| 3 |
Correct |
34 ms |
2704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8588 KB |
Output is correct |
| 3 |
Correct |
45 ms |
10700 KB |
Output is correct |
| 4 |
Correct |
48 ms |
11444 KB |
Output is correct |
| 5 |
Correct |
50 ms |
10976 KB |
Output is correct |
| 6 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 7 |
Correct |
29 ms |
920 KB |
Output is correct |
| 8 |
Correct |
34 ms |
2704 KB |
Output is correct |
| 9 |
Correct |
39 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
40 ms |
3300 KB |
Output is correct |
| 11 |
Correct |
41 ms |
3072 KB |
Output is correct |
