Submission #378293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378293	2021-03-16T12:07:46 Z	bibabas	Džumbus (COCI19_dzumbus)	C++14	Compilation error	0 ms	0 KB

dzumbus

// #define _FORTIFY_SOURCE 0 
// #pragma GCC optimize("Ofast") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("unroll-loops") 
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") 
// //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
// #pragma GCC optimize("inline") 
// #pragma GCC optimize("-fgcse") 
// #pragma GCC optimize("-fgcse-lm") 
// #pragma GCC optimize("-fipa-sra") 
// #pragma GCC optimize("-ftree-pre") 
// #pragma GCC optimize("-ftree-vrp") 
// #pragma GCC optimize("-fpeephole2") 
// #pragma GCC optimize("-ffast-math") 
// #pragma GCC optimize("-fsched-spec") 
// #pragma GCC optimize("unroll-loops") 
// #pragma GCC optimize("-falign-jumps") 
// #pragma GCC optimize("-falign-loops") 
// #pragma GCC optimize("-falign-labels") 
// #pragma GCC optimize("-fdevirtualize") 
// #pragma GCC optimize("-fcaller-saves") 
// #pragma GCC optimize("-fcrossjumping") 
// #pragma GCC optimize("-fthread-jumps") 
// #pragma GCC optimize("-funroll-loops") 
// #pragma GCC optimize("-fwhole-program") 
// #pragma GCC optimize("-freorder-blocks") 
// #pragma GCC optimize("-fschedule-insns") 
// #pragma GCC optimize("inline-functions") 
// #pragma GCC optimize("-ftree-tail-merge") 
// #pragma GCC optimize("-fschedule-insns2") 
// #pragma GCC optimize("-fstrict-aliasing") 
// #pragma GCC optimize("-fstrict-overflow") 
// #pragma GCC optimize("-falign-functions") 
// #pragma GCC optimize("-fcse-skip-blocks") 
// #pragma GCC optimize("-fcse-follow-jumps") 
// #pragma GCC optimize("-fsched-interblock") 
// #pragma GCC optimize("-fpartial-inlining") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("-freorder-functions") 
// #pragma GCC optimize("-findirect-inlining") 
// #pragma GCC optimize("-fhoist-adjacent-loads") 
// #pragma GCC optimize("-frerun-cse-after-loop") 
// #pragma GCC optimize("inline-small-functions") 
// #pragma GCC optimize("-finline-small-functions") 
// #pragma GCC optimize("-ftree-switch-conversion") 
// #pragma GCC optimize("-foptimize-sibling-calls") 
// #pragma GCC optimize("-fexpensive-optimizations") 
// #pragma GCC optimize("-funsafe-loop-optimizations") 
// #pragma GCC optimize("inline-functions-called-once") 
// #pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>

using namespace std;
         
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
#define base complex<ld>
 
using namespace std;
const ll INF = (ll)2e9;
const ll inf = (ll)1e18;
const ld eps = (ld)1e-12;
const ll mod = (ll)1e9 + 7;
const ll p = 31;
const ll mod2 = (ll)1e9 + 7;
const ll MAXN = (ll)1000 + 3;
const ll MAXC = (ll)1e6 + 11;
const ll MAXE = (ll)100;
const ll MAXLOG = (ll)19;
const ll asci = (ll)256;
const ll block = 31623;
const ld PI = acos(-1LL);
const ld e = 2.7182818284;
         
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<
// pii,
// null_type,
// less<pii>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;

ll int_rand() {
    if (RAND_MAX == (1LL << 15) - 1LL) {
        return (rand() << 15) + rand();
    }
    return rand();
}

ll ll_rand() {
    return ((ll)int_rand() << 30LL) + int_rand();
}

istream& operator >>(istream &in, pii &x) {
    cin >> x.first >> x.second;
    return in;
}
         
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
}

ll dp[MAXN][MAXN];
ll dp_h[MAXN][MAXN][2];
ll dp_take[MAXN][MAXN][2];
ll ans[MAXN];
ll sz[MAXN];
vi graph[MAXN];
ll cost[MAXN];
ll used[MAXN];

void dp_calc(ll v, ll p = -1) {
    dp_h[v][0][0] = cost[v];
    dp[v][0] = 0;
    if ((p == -1 && graph[v].size() == 0) || (p != -1 && graph[v].size() <= 1)) {
        sz[v] = 1; 
        return;
    }
    dp_take[v][0][0] = 0;
    for (ll u : graph[v]) {
        if (p == u) continue;
        dp_calc(u, v);
        for (ll ws = sz[v] + sz[u]; ws > -1; --ws) {
            for (ll w1 = min(0LL, ws - sz[u]); w1 <= sz[v]; ++w1) {
                ll w2 = ws - w1;
                mn(dp[v][w1 + w2], dp[v][w1] + dp[u][w2]);
                mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
                mn(dp_take[v][w1 + w2][1], dp_take[v][w1][0] + min(dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]));
                mn(dp_take[v][w1 + w2][0], dp_take[v][w1][0] + dp[u][w2]);
            }
        }
        sz[v] += sz[u];
    }
    ++sz[v];
    for (ll w = 0; w <= sz[v]; ++w) {
        for (ll c = 0; c < 2; ++c) {
            mn(dp_h[v][w + c][c], dp_take[v][w][c] + cost[v]);
            mn(dp[v][w + c], dp_h[v][w + c][c]);
        }
    }
}

void solve() {
    for (ll i = 0; i < MAXN; ++i) {
        ans[i] = inf;
        for (ll k = 0; k < 2; ++k) {
            for (ll j = 0; j < MAXN; ++j) {
                dp_h[i][j][0] = inf;
                dp_h[i][j][1] = inf;
                dp_take[i][j][0] = inf;
                dp_take[i][j][1] = inf;
                dp[i][j] = inf;
            }
        }
    }
    ll n, m; cin >> n >> m;
    for (ll i = 0; i < n; ++i) cin >> cost[i];
    for (ll i = 0; i < m; ++i) {
        ll v, u; cin >> v >> u;
        --v, --u;
        graph[v].push_back(u);
        graph[u].push_back(v);
    }
    vi headers;
    for (ll i = 0; i < n; ++i) {
        if (!sz[i]) {
            dp_calc(i);
            headers.push_back(i);
        }
    }
    ans[0] = 0;
    ll sz_ans = 0;
    for (ll i : headers) {
        for (ll w = 0; w <= sz_ans; ++w) {
            for (ll wn = 0; wn <= sz[i]; ++wn) {
                mn(ans[w + wn], ans[w] + dp[i][wn]);
            }
        }
        sz_ans += sz[i];
    }
    ll q; cin >> q;
    while (q--) {
        ll d; cin >> d;
        cout << upper_bound(ans, ans + MAXN, d) - ans - 1 << "\n";
    }
}

signed main() {
    srand(time(0LL));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr); 
#endif
    cout.precision(30);
    
    solve();

    return 0LL;
}

Compilation message

dzumbus.cpp: In function 'void dp_calc(long long int, long long int)':
dzumbus.cpp:144:101: error: no matching function for call to 'max(long long int, int)'
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                     ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:144:101: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                     ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:144:101: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                     ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:144:101: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                     ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:144:101: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                     ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
dzumbus.cpp:144:123: error: no matching function for call to 'min(<brace-enclosed initializer list>)'
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                                           ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  198 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:144:123: note:   candidate expects 2 arguments, 1 provided
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                                           ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  246 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:144:123: note:   candidate expects 3 arguments, 1 provided
  144 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]}));
      |                                                                                                                           ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3444 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3450 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:145:89: error: no matching function for call to 'max(long long int, int)'
  145 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][0] + min(dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]));
      |                                                                                         ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:145:89: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  145 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][0] + min(dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]));
      |                                                                                         ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:145:89: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  145 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][0] + min(dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]));
      |                                                                                         ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:145:89: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  145 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][0] + min(dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]));
      |                                                                                         ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dzumbus.cpp:51:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
dzumbus.cpp:145:89: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  145 |                 mn(dp_take[v][w1 + w2][1], dp_take[v][w1][0] + min(dp_h[u][max(w2 - 1, 0)][0], dp_h[u][w2][1]));
      |                                                                                         ^
dzumbus.cpp:65:29: note: in definition of macro 'mn'
   65 | #define mn(a, b) a = min(a, b)
      |                             ^