oj.uz

Submission #924310

# Submission time Handle Problem Language Result Execution time Memory
924310 2024-02-08T20:19:38 Z TahirAliyev The Xana coup (BOI21_xanadu) C++17
5 / 100
 95 ms 41556 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 = {0}, s2 = {0};
    int p1 = 1, p2 = 1;
    for(int to : g[node]){
        if(p == to) continue;
        dfs(to, node);
        if(dp[to][0][0] < MAX && dp[to][0][1] < MAX){
            sum += dp[to][0][0];
            s.push_back(dp[to][0][1] - dp[to][0][0]);
        }
        else if(dp[to][0][0] < MAX){
            sum += dp[to][0][0];
        }
        else if(dp[to][0][1] < MAX){
            sum += dp[to][0][1];
            p1 ^= 1;
        }
        else{
            sum = oo;
        }
        if(dp[to][1][0] < MAX && dp[to][1][1] < MAX){
            sum2 += dp[to][1][0];
            s2.push_back(dp[to][1][1] - dp[to][1][0]);
        }
        else if(dp[to][1][0] < MAX){
            sum2 += dp[to][1][0];
        }
        else if(dp[to][1][1] < MAX){
            sum2 += dp[to][1][1];
            p2 ^= 1;
        }
        else{
            sum2 = oo;
        }
    }
    sort(s.begin(), s.end());
    sort(s2.begin(), s2.end());
    ll pre = 0;
    for(int i = 0; i < s.size(); i++){
        pre += s[i];
        if(i % 2 == p1){
            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 % 2 == p2){
            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:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
xanadu.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < s2.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 2 ms 7772 KB Output is correct
8 Correct 3 ms 8024 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7860 KB Output is correct
11 Correct 2 ms 7772 KB Output is correct
12 Incorrect 2 ms 7772 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7772 KB Output is correct
7 Correct 2 ms 7772 KB Output is correct
8 Correct 3 ms 8024 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7860 KB Output is correct
11 Correct 2 ms 7772 KB Output is correct
12 Incorrect 2 ms 7772 KB Output isn't correct
13 Halted 0 ms 0 KB -