Submission #794020

# Submission time Handle Problem Language Result Execution time Memory
794020 2023-07-26T08:47:51 Z 이동현(#10060) Travelling Trader (CCO23_day2problem2) C++17
0 / 25
11 ms 24020 KB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = (int)2e5 + 4;
int n, k;
vector<int> way[NS];
int a[NS];
int dp[NS][4], from[NS][4][3];

void sol(int x, int pr){
    int sum = 0;

    for(int i = 0; i < (int)way[x].size(); ++i){
        if(way[x][i] == pr){
            swap(way[x][i], way[x].back());
            way[x].pop_back();
            break;
        }
    }
    for(auto&nxt:way[x]){
        sol(nxt, x);

        sum += a[nxt];
    }

    for(auto&nxt:way[x]){
        if(dp[nxt][2] + sum - a[nxt] > dp[x][1]){
            dp[x][1] = dp[nxt][2] + sum - a[nxt];
            
            from[x][1][0] = nxt;
        }
        if(dp[nxt][1] + sum - a[nxt] > dp[x][2]){
            dp[x][2] = dp[nxt][1] + sum - a[nxt];

            from[x][2][0] = nxt;
        }

        if(dp[nxt][3] > dp[x][0]){
            dp[x][0] = dp[nxt][3];

            from[x][0][0] = nxt, from[x][0][1] = -1;
        }
    }

    for(int i = 0; i < (int)way[x].size(); ++i){
        for(int j = 0; j < (int)way[x].size(); ++j){
            if(i == j) continue;

            int val = dp[way[x][i]][2] + dp[way[x][j]][0] + sum - a[way[x][i]] - a[way[x][j]];
            if(val > dp[x][0]){
                dp[x][0] = val;

                from[x][0][0] = way[x][i], from[x][0][1] = way[x][j];
            }
        }
    }
    for(auto&i:way[x]){
        for(auto&j:way[x]){
            for(auto&k:way[x]){
                if(i == j || j == k || i == k) continue;

                int val = dp[i][1] + dp[j][2] + dp[k][0] + sum - a[i] - a[j] - a[k];
                if(val > dp[x][3]){
                    dp[x][3] = val;
                    from[x][3][0] = i;
                    from[x][3][1] = j;
                    from[x][3][2] = k;
                }
            }
        }
    }

    for(auto&i:way[x]){
        for(auto&j:way[x]){
            for(auto&k:way[x]){
                if(i == j || j == k || i == k) continue;

                int val = dp[i][1] + dp[j][3] + sum - a[i] - a[j];
                if(val > dp[x][3]){
                    dp[x][3] = val;
                    from[x][3][0] = i;
                    from[x][3][1] = j;
                    from[x][3][2] = -1;
                }
            }
        }
    }

    if(dp[x][0] > dp[x][3]){
        dp[x][3] = dp[x][0];
        from[x][3][0] = x, from[x][3][1] = -1;
    }

    dp[x][0] += a[x];
    dp[x][1] += a[x];
    dp[x][2] += a[x];
    dp[x][3] += a[x];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    memset(from, -1, sizeof(from));

    cin >> n >> k;
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    sol(0, -1);

    cout << dp[0][0] << '\n';

    vector<int> ans;
    auto makeout = [&](auto&&self, int A, int B)->void{
        if(from[A][B][0] == -1){
            ans.push_back(A);
            return;
        }

        if(B == 1){
            ans.push_back(A);
            self(self, from[A][B][0], 2);
            for(auto&nxt:way[A]){
                if(nxt != from[A][B][0]){
                    ans.push_back(nxt);
                }
            }
        }
        else if(B == 2){
            for(auto&nxt:way[A]){
                if(nxt != from[A][B][0]){
                    ans.push_back(nxt);
                }
            }
            self(self, from[A][B][0], 1);
            ans.push_back(A);
        }
        else if(B == 0){
            ans.push_back(A);
            if(from[A][B][1] == -1){
                self(self, from[A][B][0], 3);
            }
            else{
                self(self, from[A][B][0], 2);
                for(auto&nxt:way[A]){
                    if(nxt != from[A][B][0] && nxt != from[A][B][1]){
                        ans.push_back(nxt);
                    }
                }
                self(self, from[A][B][1], 0);
            }
        }
        else{
            if(from[A][B][1] == -1){
                self(self, from[A][B][0], 0);
            }
            else if(from[A][B][2] == -1){
                for(auto&nxt:way[A]){
                    if(nxt != from[A][B][0] && nxt != from[A][B][1]){
                        ans.push_back(nxt);
                    }
                }
                self(self, from[A][B][0], 1);
                ans.push_back(A);
                self(self, from[A][B][1], 3);
            }
            else{
                for(auto&nxt:way[A]){
                    if(nxt != from[A][B][0] && nxt != from[A][B][1] && nxt != from[A][B][2]){
                        ans.push_back(nxt);
                    }
                }
                self(self, from[A][B][0], 1);
                ans.push_back(A);
                self(self, from[A][B][1], 2);
                self(self, from[A][B][2], 0);
            }
        }
    };
    makeout(makeout, 0, 0);

    cout << (int)ans.size() << '\n';
    for(auto&i:ans){
        cout << i + 1 << ' ';
    }
    cout << '\n';
    
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Incorrect 11 ms 23836 KB x_1 and x_2 are too far apart
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 23708 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Incorrect 10 ms 23816 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 23708 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Incorrect 10 ms 23816 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 23708 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Incorrect 10 ms 23816 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 24020 KB Output is correct
2 Correct 10 ms 24020 KB Output is correct
3 Incorrect 10 ms 23984 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 24020 KB Output is correct
2 Correct 10 ms 24020 KB Output is correct
3 Incorrect 10 ms 23984 KB Output isn't correct
4 Halted 0 ms 0 KB -