제출 #1289338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289338		monaxia	Dostavljač (COCI18_dostavljac)	C++20	0 / 140	1 ms	576 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 dp[505][2];

void dfs(int node, int pr, int add){
    int dp1[m + 1];
    memset(dp1, -0x3f3f3f3f3f, sizeof(dp1));

    for(int j = add + 1; j <= m; j ++){
        dp1[j] = max({dp[j][0], dp[j - add - 1][0] + val[node]});
    }

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

    for(auto& x : graph[node]) if(x != pr) dfs(x, node, add + 2);
}

void solve(){
    memset(p, -1, sizeof(p));
    memset(dp, -0x3f3f3f3f3f, sizeof(dp));

    dp[0][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, 0);

    int ans = 0;

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

    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?

컴파일 시 표준 에러 (stderr) 메시지

dostavljac.cpp: In function 'void dfs(int, int, int)':
dostavljac.cpp:82:17: warning: overflow in conversion from 'long int' to 'int' changes value from '-271644049215' to '-1061109567' [-Woverflow]
   82 |     memset(dp1, -0x3f3f3f3f3f, sizeof(dp1));
      |                 ^~~~~~~~~~~~~
dostavljac.cpp: In function 'void solve()':
dostavljac.cpp:95:16: warning: overflow in conversion from 'long int' to 'int' changes value from '-271644049215' to '-1061109567' [-Woverflow]
   95 |     memset(dp, -0x3f3f3f3f3f, sizeof(dp));
      |                ^~~~~~~~~~~~~
dostavljac.cpp: In function 'int main()':
dostavljac.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen("INVEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dostavljac.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen("INVEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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