oj.uz

Submission #794316

# Submission time Handle Problem Language Result Execution time Memory
794316 2023-07-26T12:29:02 Z 79brue Travelling Trader (CCO23_day2problem2) C++17
11 / 25
 213 ms 49760 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 9 ms 14420 KB Output is correct
2 Correct 9 ms 14388 KB Output is correct
3 Correct 99 ms 24760 KB Output is correct
4 Correct 113 ms 24712 KB Output is correct
5 Correct 131 ms 24700 KB Output is correct
6 Correct 102 ms 25292 KB Output is correct
7 Correct 76 ms 25316 KB Output is correct
8 Correct 91 ms 24892 KB Output is correct
9 Correct 144 ms 39240 KB Output is correct
10 Correct 145 ms 31944 KB Output is correct
11 Correct 72 ms 24560 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 14428 KB Output is correct
2 Correct 7 ms 14448 KB Output is correct
3 Incorrect 9 ms 14452 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 14428 KB Output is correct
2 Correct 7 ms 14448 KB Output is correct
3 Incorrect 9 ms 14452 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 14428 KB Output is correct
2 Correct 7 ms 14448 KB Output is correct
3 Incorrect 9 ms 14452 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 8 ms 14548 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 8 ms 14576 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 10 ms 14440 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 14592 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14548 KB Output is correct
14 Correct 9 ms 14512 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 8 ms 14512 KB Output is correct
17 Correct 9 ms 14580 KB Output is correct
18 Correct 8 ms 14548 KB Output is correct
19 Correct 9 ms 14548 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 8 ms 14548 KB Output is correct
22 Correct 8 ms 14720 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 8 ms 14548 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 8 ms 14576 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 10 ms 14440 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 14592 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14548 KB Output is correct
14 Correct 9 ms 14512 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 8 ms 14512 KB Output is correct
17 Correct 9 ms 14580 KB Output is correct
18 Correct 8 ms 14548 KB Output is correct
19 Correct 9 ms 14548 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 8 ms 14548 KB Output is correct
22 Correct 8 ms 14720 KB Output is correct
23 Correct 8 ms 14548 KB Output is correct
24 Correct 213 ms 30360 KB Output is correct
25 Correct 149 ms 30320 KB Output is correct
26 Correct 176 ms 30504 KB Output is correct
27 Correct 153 ms 30404 KB Output is correct
28 Correct 151 ms 30404 KB Output is correct
29 Correct 154 ms 30928 KB Output is correct
30 Correct 130 ms 29376 KB Output is correct
31 Correct 164 ms 30964 KB Output is correct
32 Correct 128 ms 29272 KB Output is correct
33 Correct 169 ms 31120 KB Output is correct
34 Correct 131 ms 29348 KB Output is correct
35 Correct 107 ms 28488 KB Output is correct
36 Correct 144 ms 30772 KB Output is correct
37 Correct 124 ms 29044 KB Output is correct
38 Correct 138 ms 28744 KB Output is correct
39 Correct 213 ms 49760 KB Output is correct
40 Correct 211 ms 38312 KB Output is correct
41 Correct 177 ms 33328 KB Output is correct
42 Correct 178 ms 34212 KB Output is correct
43 Correct 154 ms 32124 KB Output is correct
44 Correct 189 ms 31140 KB Output is correct
45 Correct 96 ms 30008 KB Output is correct
46 Correct 95 ms 28996 KB Output is correct