oj.uz

Submission #1083484

# Submission time Handle Problem Language Result Execution time Memory
1083484 2024-09-03T09:45:45 Z Requiem Chase (CEOI17_chase) C++17
100 / 100
 236 ms 163380 KB 
#include<bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define ii pair<int, int>
#define iii pair<int, ii>
#define pb push_back
#define fi first
#define se second
#define MASK(i) (1LL << i)
#define BIT(x, i) (((x) >> (i))&1)
#define TASKNAME "chase"
using namespace std;

/**
Cho cay n dinh va so o banh mi v.

Dinh i co chua pi con chim bo cau.

Khi dung 1 o banh mi o dinh u thi nhung con chim bo cau o cac dinh ke u se di den u.


Tim 1 duong di đơn u1, u2, ..., uk. Gọi sumN(ui) la tong cua nhung dinh lien ke ui ma khong nam tren duong di
ma ta rải bánh mì thì kết quả của ta là:
sumN(ui).

v <= 100
n <= 1e5.

subtask 1: n <= 10.

subtask 2: n <= 1000.

Nhận xét: ta có n^2 đường đi.
Giả sử ta xuất phát từ đỉnh i.
Ta chỉ cần dùng thêm dp[u][v][1]: xét đến đỉnh u, ta đã dùng v ổ bánh mì và liệu đỉnh bố
có dùng bánh mì không.

subtask 3: 1 đường đi xuất phát ở 1. Giải như subtask 2
subtask 4: n <= 1e5.
Ta cần giải trong O(N.v)

Ta giải kiểu gì nhỉ.
Bây giờ ta không thể thay đổi gốc thì chắc ta phải tìm cách giải bài toán trong cây con gốc u.

Nhận xét của ta là đi lên hay đi xuống không quan trọng Với 1 đường đi thì thứ quan trọng là những
vị trí ta rải bánh mì.

Nhận xét của ta là: nếu ta đi qua đỉnh u thì kết quả của ta sẽ phụ thuộc vào kết quả của đỉnh v1 và v2
mà ta chọn

Ta muốn đường đi của ta phải đi qua u:
- Có các trường hợp sau: đường đi thẳng lên từ u.
- đường đi thẳng lên u từ v1 xong đi xuống v2.

gọi up[v][j]: đường đi có trọng số lớn nhất lên v chỉ trong cây con gốc v.
dp[u][j] = up[v1][j1] + up[v2][j2] + pv (v khac v1, v khac v2, j = j1 + j2 + 1).
up[u][j] = max(up[v][j] + ...)
chắc khoảng n * v ^ 2.
**/

template<typename T> bool maximize(T &a, T b){  if (a < b) { a= b; return true; } else return false;}
const int MAXN = 3e5 + 9;
vector<int> g[MAXN];
int p[MAXN];
int n, numBread;

namespace subtask1{
    bool check(){
         return n <= 1000;
    }

    int dp[1003][103], ans = 0;

    void dfs(int u, int pa){

        int sumNeighbour = 0;
        for(int v: g[u]){
            if (v == pa) continue;
            sumNeighbour += p[v];
        }

        for(int v: g[u]){
            if (v == pa) continue;
            FOR(j, 0, numBread){
                maximize(dp[v][j], dp[u][j]);
                maximize(dp[v][j + 1], dp[u][j] + sumNeighbour); //voi nhung thang da di qua thi sumNeighbor se
                                                                 //khong co tac dung gi nhung sumNeighbor co the
                                                                 //lam giam trong so cua thg Jerry.
                maximize(ans, dp[v][j]);
                if (j + 1 <= numBread) maximize(ans, dp[v][j + 1]);
            }
            dfs(v, u);
        }
    }
    void solve(){
        FOR(i, 1, n){
            FOR(j, 1, n){
                FOR(t, 1, numBread){
                    dp[j][t] = 0;
                }
            }
            dfs(i, -1);
        }
        printf("%lld\n", ans);
    }
}

namespace subtask2{
    bool check(){
        return true;
    }

    /**
    dp[u][i]: duong di di qua dinh u.
    tu subtask 1, ta thay dp[v][i] = max(dp[u][i], dp[u][i - 1] + sumNeighBor[u])

    Ta định nghĩa laij SumNeighBor[u]: tong nhung dinh v ke u
    Gia su ta muon duong di cua minh phai di qua u.

    Các trường hợp đường thẳng:
       Ta có các trường hợp: Duong di xuat phat tu u.
       Trường hợp tiếp theo: xuất phát từ 1 đình nằm trong cây con của u.
    trường hợp ghép:
       Đi lên từ 1 đỉnh trong u và đi xuống từ 1 đỉnh trong v.

    Trước hết, ta gọi up[u][j]: dường đi xuất phát từ u đi lên đỉnh u và đã sử dụng j ổ bánh mì
                      down[u][j]: đường đi xuất phát từ u đi xuống 1 đỉnh trong cây con gốc u và ....

    down[u][j] = max(down[v][j], down[v][j - 1] + sumNeighBor[u] - p[parU])
    up[u][j] = max(up[v][j], up[v][j - 1] + sumNeighBor[u] - p[v]).
    Trạng thái kết hợp:

    Với đỉnh u:
    up[v1][j] + down[v2][k] + sumNeighbor[u] - p[v1]. Neu u rai banh mi
    up[v1][j] + down[v2][k] neu u khong rai banh mi.

    Khi giải mấy bài đường đi như này thì có 2 kiểu:
    - centroid
    - dp trên cây, cố định đường đi qua gốc đó.
    Bài này ta dựa vào up và down là các đường đi xuất phát và đi lên u.
    **/

    int up[MAXN][102], down[MAXN][102], sumNeighbor[MAXN];
    int mxDown[102], ans = 0;
    void dfs(int u, int pa){
        for(int v: g[u]){
            sumNeighbor[u] += p[v];
        }
        for(int v: g[u]){
            if (v == pa) continue;
            dfs(v, u);
            FOR(j, 0, numBread){
                maximize(down[u][j], down[v][j]);
                if (j > 0) {
                    maximize(down[u][j], down[v][j - 1] + sumNeighbor[u] - p[pa]);
                    maximize(ans, down[v][j - 1] + sumNeighbor[u]);
                }
                if (j > 0) maximize(down[u][j], down[u][j - 1]);
            }

            FOR(j, 0, numBread){
                maximize(up[u][j], up[v][j]);
                if (j > 0) maximize(up[u][j], up[v][j - 1] + sumNeighbor[u] - p[v]);
                if (j > 0) maximize(up[u][j], up[u][j - 1]);
            }
        }
        maximize(up[u][1], sumNeighbor[u]);
        FOR(i, 0, numBread) {
            maximize(ans, down[u][i]);
            maximize(ans, up[u][i]);
        }

        for(int v: g[u]){
            if (v != pa){
                FOR(j, 0, numBread){
                    maximize(ans, mxDown[j] + up[v][numBread - j]);
                    if (numBread - j - 1 >= 0) {
                        maximize(ans, mxDown[j] + up[v][numBread - j - 1] + sumNeighbor[u] - p[v]);
                    }
                }
                FOR(j, 0, numBread){
                    maximize(mxDown[j], down[v][j]);
                }

            }
        }
        FOR(j, 0, numBread){
            mxDown[j] = 0;
        }
        reverse(g[u].begin(), g[u].end());
        for(int v: g[u]){
            if (v != pa){
                FOR(j, 0, numBread){
                    maximize(ans, mxDown[j] + up[v][numBread - j]);
                    if (numBread - j - 1 >= 0) {
                        maximize(ans, mxDown[j] + up[v][numBread - j - 1] + sumNeighbor[u] - p[v]);
                    }
                }
                FOR(j, 0, numBread){
                    maximize(mxDown[j], down[v][j]);
                }

            }
        }
        FOR(j, 0, numBread){
            mxDown[j] = 0;
        }
//        printf("CUR %lld %lld\n", u, ans);
//
//        printf("UP \n");
//        FOR(i, 0, numBread){
//            printf("%lld ", up[u][i]);
//        }
//        printf("\nDOWN \n");
//
//        FOR(i, 0, numBread){
//            printf("%lld ", down[u][i]);
//        }
//        printf("\n");
    }
    void solve(){
        dfs(1, -1);
        printf("%lld\n", ans);
    }
}
main(){
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> numBread;
    FOR(i, 1, n){
        cin >> p[i];
    }
    FOR(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

//    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
}

Compilation message

chase.cpp:229:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  229 | main(){
      | ^~~~
chase.cpp: In function 'int main()':
chase.cpp:232:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:233:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 3 ms 7492 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 3 ms 7492 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 5 ms 8796 KB Output is correct
8 Correct 4 ms 8644 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 5 ms 9052 KB Output is correct
11 Correct 4 ms 9052 KB Output is correct
12 Correct 4 ms 8856 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 141520 KB Output is correct
2 Correct 191 ms 141556 KB Output is correct
3 Correct 171 ms 94952 KB Output is correct
4 Correct 120 ms 161324 KB Output is correct
5 Correct 236 ms 162988 KB Output is correct
6 Correct 226 ms 163116 KB Output is correct
7 Correct 234 ms 163152 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 3 ms 7492 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 5 ms 8796 KB Output is correct
8 Correct 4 ms 8644 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 5 ms 9052 KB Output is correct
11 Correct 4 ms 9052 KB Output is correct
12 Correct 4 ms 8856 KB Output is correct
13 Correct 197 ms 141520 KB Output is correct
14 Correct 191 ms 141556 KB Output is correct
15 Correct 171 ms 94952 KB Output is correct
16 Correct 120 ms 161324 KB Output is correct
17 Correct 236 ms 162988 KB Output is correct
18 Correct 226 ms 163116 KB Output is correct
19 Correct 234 ms 163152 KB Output is correct
20 Correct 220 ms 163112 KB Output is correct
21 Correct 73 ms 94804 KB Output is correct
22 Correct 228 ms 163072 KB Output is correct
23 Correct 110 ms 161104 KB Output is correct
24 Correct 227 ms 163380 KB Output is correct
25 Correct 170 ms 94660 KB Output is correct
26 Correct 195 ms 141648 KB Output is correct
27 Correct 188 ms 141648 KB Output is correct