Submission #1289390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289390		monaxia	Dostavljač (COCI18_dostavljac)	C++20	140 / 140	210 ms	2492 KiB

dostavljac

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds; 

using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr ull Mod = (119 << 23) | 1;
constexpr ull sqr = 223;
constexpr ld eps = 1e-9;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long random_ll(long long l, long long r) {if (l > r) return -1; return uniform_int_distribution<long long>(l, r)(rng);}

int n, m;
vector <int> graph[505];
int sub[505], phd[505], h[505], p[505][10], val[505];
int timer = 0;

void dfs1(int node, int pr){
    sub[node] = 1;
    phd[++ timer] = node;
    h[node] = h[pr] + 1;
    p[node][0] = pr;

    for(int i = 1; i <= __lg(n); i ++) if(p[node][i - 1] != -1) p[node][i] = p[p[node][i - 1]][i - 1];

    for(int x : graph[node]) if(x != pr){
        dfs1(x, node); 
        sub[node] += sub[x];
    }
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    

    while(h[u] > h[v]){
        u = p[u][__lg(h[u] - h[v])];
    }
 
    if(u == v) return u;
 
    for(int i = __lg(n); i >= 1; i --){
        if(p[u][i] != p[v][i]){
            u = p[u][i];
            v = p[v][i];
        }
    }
 
    while(u != v){
        u = p[u][0];
        v = p[v][0];
    }
 
    return u;
}

int dist(int u, int v){
    int pr = lca(u, v);

    return h[u] + h[v] - h[pr] * 2;
}

int dp0[505][505], dp1[505][505];

void dfs(int node, int pr){
    int dpt0[505], dpt1[505];

    dp0[node][1] = dp1[node][1] = val[node];

    for(auto& x : graph[node]){
        if(x == pr) continue;
        dfs(x, node);

        for(int i = 0; i <= m; i ++){
            dpt1[i] = dp1[node][i];
            dpt0[i] = dp0[node][i];
        }

        for(int i = m; i >= 0; i --){
            for(int j = 0; j <= m; j ++){
                if(i >= j + 2){
                    dp0[node][i] = max(dp0[node][i], dp0[node][i - j - 2] + dp0[x][j]);
                    dp1[node][i] = max(dp1[node][i], dp1[node][i - j - 2] + dp0[x][j]);

                    // cout << dp0[node][i - j - 2] + dp0[x][j] << "\n";
                }

                if(i >= j + 1) dp1[node][i] = max(dp1[node][i], dp0[node][i - j - 1] + dp1[x][j]);
            }
        }
    
        // cout << node << ": ";    for(int i = 1; i <= m; i ++) cout << dp1[node][i] << " "; cout << "\n";
    }

    for(int i = 1; i <= m; i ++) dp1[node][i] = max(dp1[node][i], dp1[node][i - 1]);
    for(int i = 1; i <= m; i ++) dp0[node][i] = max(dp0[node][i], dp0[node][i - 1]);

}

void solve(){
    memset(p, -1, sizeof(p));
    memset(dp0, 0, sizeof(dp0));
    memset(dp1, 0, sizeof(dp1));

    dp0[1][0] = dp1[1][0] = 0;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++) cin >> val[i];

    for(int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        graph[v].pb(u);
        graph[u].pb(v);
    }

    dfs1(1, 0);
    dfs(1, 0);

    int ans = 0;

    for(int i = 0; i <= m; i ++) ans = max(ans, dp1[1][i]);

    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    if(fopen("INVEST.inp", "r")){
        freopen("INVEST.inp", "r", stdin);
        freopen("INVEST.out", "w", stdout);
    }

    int t = 1;

    // cin >> t;

    while(t --){
        solve();
        cout << "\n";
    }

    cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

// Whose eyes are those eyes?

Compilation message (stderr)

dostavljac.cpp: In function 'int main()':
dostavljac.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen("INVEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dostavljac.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen("INVEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14