oj.uz

Submission #924316

# Submission time Handle Problem Language Result Execution time Memory
924316 2024-02-08T20:37:45 Z TahirAliyev The Xana coup (BOI21_xanadu) C++17
10 / 100
 97 ms 35628 KB 
#include <bits/stdc++.h>

#define ll long long
using namespace std;
#define pii pair<ll, ll>
ll oo = 1e18 + 9;
int n, m, k;
const int MAX = 2e5 + 5, MOD = 1e9 + 7, LOGMAX = 25;

vector<int> g[MAX];
int col[MAX];

ll dp[MAX][2][2];

void dfs(int node, int p){
    dp[node][0][0] = oo;
    dp[node][0][1] = oo;
    dp[node][1][0] = oo;
    dp[node][1][1] = oo;

    ll sum = 0, sum2 = 0;
    vector<ll> s, s2;
    int cnt = 0, cnt2 = 0;
    for(int to : g[node]){
        if(p == to) continue;
        dfs(to, node);
        if(dp[to][0][1] > MAX && dp[to][0][0] > MAX){
            sum = oo;
        }
        else{
            sum += dp[to][0][0];
            s.push_back(dp[to][0][1] - dp[to][0][0]);
        }
        if(dp[to][0][1] < MAX){
            cnt++;
        }
        if(dp[to][1][1] > MAX && dp[to][1][0] > MAX){
            sum2 = oo;
        }
        else{
            sum2 += dp[to][1][0];
            s2.push_back(dp[to][1][1] - dp[to][1][0]);
        }
        if(dp[to][1][1] < MAX){
            cnt2++;
        }
    }
    sort(s.begin(), s.end());
    sort(s2.begin(), s2.end());
    s.insert(s.begin(), 0);
    s2.insert(s2.begin(), 0);
    ll pre = 0;
    for(int i = 0; i < s.size(); i++){
        pre += s[i];
        if(i < cnt) continue;
        if(i & 1){
            dp[node][0][0] = min(sum + pre, dp[node][0][0]);
        }
        else{
            dp[node][1][0] = min(sum + pre, dp[node][1][0]);
        }
    }
    pre = 0;
    for(int i = 0; i < s2.size(); i++){
        pre += s2[i];
        if(i < cnt2) continue;
        if(i & 1){
            dp[node][1][1] = min(sum2 + pre, dp[node][1][1]);
        }
        else{
            dp[node][0][1] = min(sum2 + pre, dp[node][0][1]); 
        }
    }
    dp[node][1][1]++;
    dp[node][0][1]++;
    if(!col[node]){
        swap(dp[node][0][0], dp[node][1][0]);
        swap(dp[node][0][1], dp[node][1][1]);
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) cin >> col[i];
    dfs(1, 1);
    if(min(dp[1][0][0], dp[1][0][1]) >= MAX){
        cout << "impossible\n";
    }
    else{
        cout << min(dp[1][0][0], dp[1][0][1]) << '\n';
    }
}

signed main(){
    int t = 1;
    for(int i = 1; i <= t; i++){
        solve();
    }
}

Compilation message

xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
xanadu.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < s2.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 35408 KB Output is correct
2 Correct 86 ms 35112 KB Output is correct
3 Correct 97 ms 35408 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 35408 KB Output is correct
2 Correct 94 ms 35152 KB Output is correct
3 Correct 87 ms 35628 KB Output is correct
4 Incorrect 80 ms 14928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -