oj.uz

Submission #794326

# Submission time Handle Problem Language Result Execution time Memory
794326 2023-07-26T12:39:45 Z 79brue Travelling Trader (CCO23_day2problem2) C++17
11 / 25
 210 ms 49608 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
ll arr[200002];
vector<int> link[200002];

void solvek1();
void solvek2();
void solvek3();

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    if(k==1) solvek1();
    if(k==2) solvek2();
    if(k==3) solvek3();
}

namespace solve1{
    int par[200002];
    ll depth[200002];

    void dfs(int x, int p=-1){
        depth[x] += arr[x];
        for(auto y: link[x]){
            if(y==p) continue;
            depth[y] = depth[x], par[y] = x;
            dfs(y, x);
        }
    }

    void solve(){
        dfs(1);
        int x = max_element(depth+1, depth+n+1) - depth;
        vector<int> v;
        while(x) v.push_back(x), x = par[x];
        reverse(v.begin(), v.end());
        printf("%lld\n%d\n", depth[v.back()], (int)v.size());
        for(auto x: v) printf("%d ", x);
    }
}

void solvek1(){
    solve1::solve();
}

namespace solve2{
    int par[200002];
    ll depth[200002];

    vector<int> child[200002];

    void dfsChild(int x, int p=-1){
        for(auto y: link[x]){
            if(y==p) continue;
            child[x].push_back(y), par[y] = x, depth[y] = depth[x] + 1;
            dfsChild(y, x);
        }
    }

    ll U[200002][2]; /// 돌아오는 DP, [0]은 x 부모에서 시작, [1]은 x에서 시작
    int trackU[200002][2]; /// 역추적 용도

    void dfsU(int x){
        if(child[x].empty()){ /// 리프 노드인 경우
            U[x][0] = U[x][1] = arr[x];
            return;
        }

        vector<pair<ll, int> > profit_pointToU0, profit_pointToU1;

        ll pointSum = arr[x]; /// 자기 직접 자식들의 모든 이익을 더한 값
        for(int y: child[x]){
            dfsU(y);
            pointSum += arr[y];
            profit_pointToU0.push_back(make_pair(U[y][0] - arr[y], y));
            profit_pointToU1.push_back(make_pair(U[y][1] - arr[y], y));
        }

        sort(profit_pointToU0.rbegin(), profit_pointToU0.rend());
        sort(profit_pointToU1.rbegin(), profit_pointToU1.rend());

        /// U[x][0]: 부모에서 출발해 x가 비어 있는 채로 아래를 순회하고 돌아오는 비용
        /// point 값 중 하나를 U[y][1]로 바꿀 수 있다.
        assert(profit_pointToU0[0].first >= 0);
        U[x][0] = pointSum + profit_pointToU1[0].first;
        trackU[x][0] = profit_pointToU1[0].second;

        /// U[x][1]: x에서 출발해 부모가 비어 있는 채로 아래를 순회하고 돌아오는 비용
        /// point 값 중 하나를 U[y][0]으로 바꿀 수 있다.
        assert(profit_pointToU1[0].first >= 0);
        U[x][1] = pointSum + profit_pointToU0[0].first;
        trackU[x][1] = profit_pointToU0[0].second;
    }

    ll I[200002][2]; /// 돌아오지 않는 DP, [0]은 x 부모에서 시작, [1]은 x에서 시작
    int typeI[200002][2], trackI[200002][2], trackI2[200002][2], trackI3[200002][2]; /// 역추적 용도
    bool trackDetail[200002][2]; /// 0이면 I, 1이면 U
    /// type -1: I[0]->I[1]로 바꿀 때, 0: 잔여 노드 챙기고 내려갈 때, 1: 그냥 하나로 내려갈 때

    void dfsI(int x){
        if(child[x].empty()){
            I[x][0] = I[x][1] = arr[x];
            return;
        }

        vector<pair<ll, int> > profit_pointToU0, profit_pointToU1;
        vector<pair<ll, int> > profit_pointToI0, profit_pointToI1;
        ll pointSum = arr[x];

        for(auto y: child[x]){
            dfsI(y);
            pointSum += arr[y];
            profit_pointToU0.push_back(make_pair(U[y][0] - arr[y], y));
            profit_pointToU1.push_back(make_pair(U[y][1] - arr[y], y));
            profit_pointToI0.push_back(make_pair(I[y][0] - arr[y], y));
            profit_pointToI1.push_back(make_pair(I[y][1] - arr[y], y));
        }

        sort(profit_pointToU0.rbegin(), profit_pointToU0.rend());
        sort(profit_pointToU1.rbegin(), profit_pointToU1.rend());
        sort(profit_pointToI0.rbegin(), profit_pointToI0.rend());
        sort(profit_pointToI1.rbegin(), profit_pointToI1.rend());

        /// I[x][1]: x에서 출발해 아래로 내려가는 최댓값
        /// Case 0. U[x][1]을 택한다.
        I[x][1] = U[x][1], typeI[x][1] = -2;

        /// Case 1. 자식 중 하나의 I[0]을 취할 수 있다.
        for(auto y: child[x]) if(I[x][1] < arr[x] + max(U[y][0], I[y][0])){
            I[x][1] = arr[x] + max(U[y][0], I[y][0]);
            typeI[x][1] = 1, trackI[x][1] = y, trackDetail[x][1] = U[y][0]>I[y][0];
        }

        /// Case 2. 자식 중 하나의 U[0] or U[1]을 취하고, 잔여 노드를 먹고, 남은 자식 중 하나의 I[1]을 취할 수 있다.
        for(auto a: child[x]) for(auto b: child[x]){
            if(a==b) continue;
            ll v = pointSum - arr[a] - arr[b] + max(U[a][0], U[a][1]) + max(U[b][1], I[b][1]);
            if(I[x][1] >= v) continue;
            I[x][1] = v, typeI[x][1] = 0, trackI[x][1] = a, trackI2[x][1] = b, trackDetail[x][1] = U[b][1]>I[b][1];
        }

        /// I[x][0]: x 부모에서 출발해 아래로 내려가는 최댓값
        /// Case 0. I[1]을 택한다.
        I[x][0] = I[x][1], typeI[x][0] = -1;

        /// Case 0-2. U[x][0]을 택한다.
        if(I[x][0] > U[x][0]) I[x][0] = U[x][0], typeI[x][0] = -2;

        /// Case 1. 자식 중 하나의 I[0]을 취할 수 있다.
        for(auto y: child[x]) if(I[x][0] < arr[x] + max(U[y][0], I[y][0])){
            I[x][0] = arr[x] + max(U[y][0], I[y][0]);
            typeI[x][0] = 1, trackI[x][0] = y, trackDetail[x][0] = U[y][0]>I[y][0];
        }

        /// Case 2. 자식 중 하나의 U[1]을 취하고, 잔여 노드를 먹고, 남은 자식 중 하나의 I[1]을 취할 수 있다.
        for(auto a: child[x]) for(auto b: child[x]){
            if(a==b) continue;
            ll v = pointSum - arr[a] - arr[b] + U[a][1] + max(U[b][1], I[b][1]);
            if(I[x][0] >= v) continue;
            I[x][0] = v, typeI[x][0] = 0, trackI[x][0] = a, trackI2[x][0] = b, trackDetail[x][0] = U[b][1]>I[b][1];
        }

        /// Case 3. 자식 중 하나의 U[1]을 취하고, 다른 자식의 U[0]을 취하고, 잔여 노드를 먹고, 남은 자식 중 하나의 I[1]을 취한다.
        for(auto a: child[x]) for(auto b: child[x]) for(auto c: child[x]){
            if(a==b || b==c || a==c) continue;
            ll v = pointSum - arr[a] - arr[b] - arr[c] + U[a][1] + U[b][0] + max(U[c][1], I[c][1]);
            if(I[x][0] >= v) continue;
            I[x][0] = v, typeI[x][0] = 2, trackI[x][0] = a, trackI2[x][0] = b, trackI3[x][0] = c, trackDetail[x][0] = U[c][1]>I[c][1];
        }

        /// Case 4. 자식 중 하나의 U[0]을 취하고, 잔여 노드를 먹고, 남은 자식 중 하나의 I[1]을 취한다.
        for(auto a: child[x]) for(auto b: child[x]){
            if(a==b) continue;
            ll v = pointSum - arr[a] - arr[b] - U[a][0] + max(U[b][1], I[b][1]);
            if(I[x][0] >= v) continue;
            I[x][0] = v, typeI[x][0] = 3, trackI[x][0] = a, trackI2[x][0] = b, trackDetail[x][0] = U[b][1]>I[b][1];
        }

        /// Case 5. 자식 중 하나의 U[1]을 취하고, 다른 자식의 U[0]을 취하고, 잔여 노드를 먹는다.
        for(auto a: child[x]) for(auto b: child[x]){
            if(a==b) continue;
            ll v = pointSum - arr[a] - arr[b] + U[a][1] + U[b][0];
            if(I[x][0] >= v) continue;
            I[x][0] = v, typeI[x][0] = 4, trackI[x][0] = a, trackI2[x][0] = b;
        }
    }

    vector<int> ans;

    void track(int x, char type, int j){
        if(type == 'U'){
            if(child[x].empty()) ans.push_back(x);
            else if(j==0){
                int nxt = trackU[x][j];
                for(auto y: child[x]) if(y != nxt) ans.push_back(y);
                track(nxt, 'U', 1);
                ans.push_back(x);
            }
            else if(j==1){
                int nxt = trackU[x][j];
                ans.push_back(x);
                track(nxt, 'U', 0);
                for(auto y: child[x]) if(y != nxt) ans.push_back(y);
            }
        }
        else if(type == 'I'){
            if(child[x].empty()) ans.push_back(x);
            else if(typeI[x][j] == -2) track(x, 'U', j);
            else if(typeI[x][j] == -1) track(x, 'I', !j);
            else if(j==0){
                if(typeI[x][j] == 0){
                    int a = trackI[x][j], b = trackI2[x][j];
                    track(a, 'U', 1);
                    ans.push_back(x);
                    for(auto y: child[x]) if(y!=a && y!=b) ans.push_back(y);
                    track(b, trackDetail[x][j] ? 'U' : 'I', 1);
                }
                else if(typeI[x][j] == 1){
                    int a = trackI[x][j];
                    ans.push_back(x);
                    track(a, trackDetail[x][j] ? 'U' : 'I', 0);
                }
                else if(typeI[x][j] == 2){
                    int a = trackI[x][j], b = trackI2[x][j], c = trackI3[x][j];
                    track(a, 'U', 1);
                    ans.push_back(x);
                    track(b, 'U', 0);
                    for(auto y: child[x]) if(y!=a && y!=b && y!=c) ans.push_back(y);
                    track(c, trackDetail[x][j] ? 'U' : 'I', 1);
                }
                else if(typeI[x][j] == 3){
                    int a = trackI[x][j], b = trackI2[x][j];
                    ans.push_back(x);
                    track(a, 'U', 0);
                    for(auto y: child[x]) if(y!=a && y!=b) ans.push_back(y);
                    track(b, trackDetail[x][j] ? 'U' : 'I', 1);
                }
                else if(typeI[x][j] == 4){
                    int a = trackI[x][j], b = trackI2[x][j];
                    track(a, 'U', 1);
                    ans.push_back(x);
                    track(b, 'U', 0);
                    for(auto y: child[x]) if(y!=a && y!=b) ans.push_back(y);
                }
                else exit(1);
            }
            else{
                if(typeI[x][j] == 0){
                    int a = trackI[x][j], b = trackI2[x][j];
                    ans.push_back(x);
                    track(a, 'U', 0);
                    for(auto y: child[x]) if(y!=a && y!=b) ans.push_back(y);
                    track(b, trackDetail[x][j] ? 'U' : 'I', 1);
                }
                else if(typeI[x][j] == 1){
                    int a = trackI[x][j];
                    ans.push_back(x);
                    track(a, trackDetail[x][j] ? 'U' : 'I', 0);
                }
                else exit(1);
            }
        }
    }

    void solve(){
        dfsChild(1);
        dfsU(1);
        dfsI(1);

//        printf("Dfs Results\n");
//        for(int i=1; i<=n; i++){
//            printf("%2d: U0 %2lld U1 %2lld I0 %2lld I1 %2lld\n", i, U[i][0], U[i][1], I[i][0], I[i][1]);
//        }

        printf("%lld\n", I[1][1]);
        track(1, 'I', 1);
        printf("%d\n", (int)ans.size());
        for(auto x: ans) printf("%d ", x);

        ll v = 0;
        for(auto x: ans) v += arr[x];
        assert(v == I[1][1]);
        for(int i=0; i<(int)ans.size()-1; i++){
            int x = ans[i], y = ans[i+1];
            assert(x==par[y] || y==par[x] || par[x]==par[y] || par[par[x]]==y || par[par[y]]==x);
        }

        for(int i=1; i<=n; i++) assert(U[i][0] >= U[i][1]);
//        for(int i=1; i<=n; i++) assert(typeI[i][0] < 3);

        set<int> st;
        for(auto x: ans) st.insert(x);
        assert(st.size() == ans.size());
    }
}

void solvek2(){
    solve2::solve();
}

namespace solve3{
    int par[200002];
    ll depth[200002];
    vector<int> child[200002];

    void dfs(int x, int p=-1){
        for(auto y: link[x]){
            if(y==p) continue;
            par[y] = x, depth[y] = depth[x] + 1;
            child[x].push_back(y);
            dfs(y, x);
        }
    }

    vector<int> ans;
    bool chk[200002];

    void solve(){
        dfs(1);

        int coolTime = 1;
        vector<int> vec (1, 1);
        while(!vec.empty()){
            int x = vec.back(); coolTime--;
            if(coolTime == 0){
                assert(!chk[x]);
                chk[x] = 1, ans.push_back(x), coolTime = 3;
            }
            if(child[x].empty()){
                if(!chk[x]) chk[x] = 1, ans.push_back(x), coolTime = 3;
                vec.pop_back();
            }
            else{
                int y = child[x].back(); child[x].pop_back();
                vec.push_back(y);
            }
        }

        printf("%lld\n%d\n", accumulate(arr+1, arr+n+1, 0LL), n);
        for(int x: ans) printf("%d ", x);
    }
}

void solvek3(){
    solve3::solve();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:23:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 98 ms 24708 KB Output is correct
4 Correct 105 ms 24748 KB Output is correct
5 Correct 122 ms 24600 KB Output is correct
6 Correct 97 ms 25292 KB Output is correct
7 Correct 77 ms 25376 KB Output is correct
8 Correct 92 ms 24972 KB Output is correct
9 Correct 146 ms 39232 KB Output is correct
10 Correct 164 ms 31936 KB Output is correct
11 Correct 74 ms 24476 KB Output is correct
12 Correct 7 ms 14420 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14476 KB Output is correct
3 Incorrect 7 ms 14448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14476 KB Output is correct
3 Incorrect 7 ms 14448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14476 KB Output is correct
3 Incorrect 7 ms 14448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14548 KB Output is correct
2 Correct 9 ms 14608 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14584 KB Output is correct
5 Correct 12 ms 14568 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 8 ms 14548 KB Output is correct
11 Correct 8 ms 14588 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14548 KB Output is correct
14 Correct 8 ms 14548 KB Output is correct
15 Correct 9 ms 14548 KB Output is correct
16 Correct 11 ms 14548 KB Output is correct
17 Correct 9 ms 14548 KB Output is correct
18 Correct 8 ms 14548 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 11 ms 14572 KB Output is correct
22 Correct 7 ms 14696 KB Output is correct
23 Correct 8 ms 14548 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14548 KB Output is correct
2 Correct 9 ms 14608 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14584 KB Output is correct
5 Correct 12 ms 14568 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 8 ms 14548 KB Output is correct
11 Correct 8 ms 14588 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14548 KB Output is correct
14 Correct 8 ms 14548 KB Output is correct
15 Correct 9 ms 14548 KB Output is correct
16 Correct 11 ms 14548 KB Output is correct
17 Correct 9 ms 14548 KB Output is correct
18 Correct 8 ms 14548 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 11 ms 14572 KB Output is correct
22 Correct 7 ms 14696 KB Output is correct
23 Correct 8 ms 14548 KB Output is correct
24 Correct 153 ms 30400 KB Output is correct
25 Correct 181 ms 30400 KB Output is correct
26 Correct 156 ms 30384 KB Output is correct
27 Correct 152 ms 30404 KB Output is correct
28 Correct 157 ms 30392 KB Output is correct
29 Correct 181 ms 30884 KB Output is correct
30 Correct 133 ms 29476 KB Output is correct
31 Correct 187 ms 30916 KB Output is correct
32 Correct 125 ms 29276 KB Output is correct
33 Correct 160 ms 30896 KB Output is correct
34 Correct 150 ms 29240 KB Output is correct
35 Correct 103 ms 28528 KB Output is correct
36 Correct 146 ms 30776 KB Output is correct
37 Correct 143 ms 28964 KB Output is correct
38 Correct 113 ms 28700 KB Output is correct
39 Correct 200 ms 49608 KB Output is correct
40 Correct 210 ms 38292 KB Output is correct
41 Correct 152 ms 33436 KB Output is correct
42 Correct 186 ms 34136 KB Output is correct
43 Correct 154 ms 32048 KB Output is correct
44 Correct 165 ms 31040 KB Output is correct
45 Correct 104 ms 30016 KB Output is correct
46 Correct 121 ms 29048 KB Output is correct