Submission #924325

#	Time	Username	Problem	Language	Result	Execution time	Memory
924325		TahirAliyev	The Xana coup (BOI21_xanadu)	C++17	100 / 100	87 ms	27988 KiB

xanadu

#include <bits/stdc++.h>
 
#define ll long long
using namespace std;
#define pii pair<ll, ll>
ll oo = 1e9 + 9;
int n, m, k;
const int MAX = 1e5 + 5, MOD = 1e9 + 7, LOGMAX = 25;
 
vector<int> g[MAX];
int col[MAX];
 
int 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;
 
    int sum = 0, sum2 = 0;
    vector<int> s, s2;
    int p1 = 1, p2 = 1;
    for(int to : g[node]){
        if(p == to) continue;
        dfs(to, node);
        if(dp[to][0][0] <= n && dp[to][0][1] <= n){
            sum += dp[to][0][0];
            s.push_back(dp[to][0][1] - dp[to][0][0]);
        }
        else if(dp[to][0][0] <= n){
            sum += dp[to][0][0];
        }
        else{
            sum += dp[to][0][1];
            p1 ^= 1;
        }
        if(dp[to][1][0] <= n && dp[to][1][1] <= n){
            sum2 += dp[to][1][0];
            s2.push_back(dp[to][1][1] - dp[to][1][0]);
        }
        else if(dp[to][1][0] <= n){
            sum2 += dp[to][1][0];
        }
        else{
            sum2 += dp[to][1][1];
            p2 ^= 1;
        }
    }
    sort(s.begin(), s.end());
    sort(s2.begin(), s2.end());
    int pre = 0;
    if(p1){
        dp[node][1][0] = min(sum, dp[node][1][0]);
    }
    else{
        dp[node][0][0] = min(sum, dp[node][0][0]);
    }
    for(int i = 0; i < s.size(); i++){
        pre += s[i];
        if(i % 2 == p1){
            dp[node][1][0] = min(sum + pre, dp[node][1][0]);
        }
        else{
            dp[node][0][0] = min(sum + pre, dp[node][0][0]);
        }
    }
    pre = 0;
    if(p2){
        dp[node][0][1] = min(sum2, dp[node][0][1]);
    }
    else{
        dp[node][1][1] = min(sum2, dp[node][1][1]);
    }
    for(int i = 0; i < s2.size(); i++){
        pre += s2[i];
        if(i % 2 == p2){
            dp[node][0][1] = min(sum2 + pre, dp[node][0][1]); 
        }
        else{
            dp[node][1][1] = min(sum2 + pre, dp[node][1][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]) > n){
        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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30