oj.uz

Submission #972823

# Submission time Handle Problem Language Result Execution time Memory
972823 2024-05-01T08:33:02 Z efedmrlr Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 178408 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m;
vector<int> p(N, 0), sm(N, 0);
array<vector<int>, 105> dpd, dpu;
vector<vector<int> > adj(N, vector<int>());
vector<int> pr(N, 0);
void dfs(int node, int par) {
    pr[node] = par;
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfs(c, node);
    }
    for(int k = 0; k <= m; k++) {
        for(int c : adj[node]) {
            if(c == par) continue;
            dpd[k][node] = max(dpd[k][node], dpd[k][c]);
        }
    }
    for(int k = 1; k <= m; k++) {
        for(int c : adj[node]) {
            if(c == par) continue;
            dpd[k][node] = max(dpd[k][node], dpd[k - 1][c] + sm[node] - p[c]);
        }
    } 
    for(int k = 0; k <= m; k++) {
        for(int c : adj[node]) {
            if(c == par) continue;
            dpu[k][node] = max(dpu[k][node], dpu[k][c]);
        }
    }
    for(int k = 1; k <= m; k++) {
        for(int c : adj[node]) {
            if(c == par) continue;
            dpu[k][node] = max(dpu[k][node], dpu[k - 1][c] + sm[c] - p[node]);
        }
    }
}

inline void solve() {
    cin>>n>>m;
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    for(int i = 1; i<=n; i++) {
        for(auto c : adj[i]) {
            sm[i] += p[c];
        }
    }
    REP(i, m + 3) {
        dpd[i].assign(n + 2, 0);
        dpu[i].assign(n + 2, 0);
    }
    for(int i = 1; i <= n; i++) {
        dpd[1][i] = sm[i];
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) {
        for(int k = 1; k <= m; k++) {
            dpd[k][i] = max(dpd[k][i], dpd[k - 1][i]);
            dpu[k][i] = max(dpu[k][i], dpu[k - 1][i]);
        }
    }
    // for(int i = 1; i<=n; i++) {
    //     cout << "i:" << i << " dpd:" << dpd[2][i] << "\n";
    // }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int v = 0; v <= m; v++) {
            int v2 = m - v;
            vector<array<int, 2> > dmax, umax;
            int tmp = 0;
            if(v > 0) tmp = sm[i];
            dmax.pb({tmp, -1}); umax.pb({0, -2});
            dmax.pb({tmp, -4}); umax.pb({0, -3});
            for(auto c : adj[i]) {
                if(pr[i] == c) continue;
                int ret = dpd[v][c];
                if(v > 0) {
                    ret = max(ret, dpd[v - 1][c] + sm[i] - p[c]);
                }
                dmax.pb({ret, c});
                ret = dpu[v2][c];
                if(v2 > 0) {
                    ret = max(ret, dpu[v2 - 1][c] + sm[c] - p[i]);
                }
                umax.pb({ret, c});
            }
            sort(rall(dmax));
            sort(rall(umax));
            if(dmax[0][1] == umax[0][1]) swap(dmax[0], dmax[1]);
            ans = max(ans, dmax[0][0] + umax[0][0]);
            ans = max(ans, dmax[1][0] + umax[1][0]);
        }
    }
    cout << ans << "\n";
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4964 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4964 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 21 ms 6744 KB Output is correct
8 Correct 4 ms 5216 KB Output is correct
9 Correct 4 ms 5212 KB Output is correct
10 Correct 25 ms 6748 KB Output is correct
11 Correct 8 ms 5720 KB Output is correct
12 Correct 5 ms 5212 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3213 ms 175932 KB Output is correct
2 Correct 3086 ms 175924 KB Output is correct
3 Correct 3150 ms 178408 KB Output is correct
4 Correct 86 ms 17056 KB Output is correct
5 Execution timed out 4029 ms 171228 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4964 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 21 ms 6744 KB Output is correct
8 Correct 4 ms 5216 KB Output is correct
9 Correct 4 ms 5212 KB Output is correct
10 Correct 25 ms 6748 KB Output is correct
11 Correct 8 ms 5720 KB Output is correct
12 Correct 5 ms 5212 KB Output is correct
13 Correct 3213 ms 175932 KB Output is correct
14 Correct 3086 ms 175924 KB Output is correct
15 Correct 3150 ms 178408 KB Output is correct
16 Correct 86 ms 17056 KB Output is correct
17 Execution timed out 4029 ms 171228 KB Time limit exceeded
18 Halted 0 ms 0 KB -