Submission #1028095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028095		hasan2006	The Xana coup (BOI21_xanadu)	C++17	100 / 100	71 ms	23636 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e5 + 9 , mod = 1e9 + 7;
ll  dp[N][3][3] , a[N] , b[N];
vector<int>v[N];
void dfs(int n , int p =0){
    for(auto to : v[n])
        if(to != p)
            dfs(to , n);
    for(int x = 0; x < 2; x++){
        for(int y = 0; y < 2; y++){
            b[0]  = b[1] = b[3] = b[4] =  0;
            b[2] = 1e18;
            for(auto to : v[n]){
                if(to == p)
                    continue;
                if(dp[to][y][0] != -1 && dp[to][y][1] != -1){
                    b[2] = min({b[2] , abs(dp[to][y][0] - dp[to][y][1])});
                    if(dp[to][y][0] >= dp[to][y][1])
                        b[1]++ , b[0] += dp[to][y][1];
                    else
                        b[4] += dp[to][y][0];
                }else if(dp[to][y][0] == -1 && dp[to][y][1] == -1){
                    b[3]++;
                }else if(dp[to][y][1] != -1)
                    b[1]++ , b[0] += dp[to][y][1];
                else
                    b[4] += dp[to][y][0];
            }
            int f = abs(x - ((a[n] + y) % 2));
            if(b[3])
                dp[n][x][y] = -1;
            else if(b[1] % 2 == f || b[2] != 1e18)
                dp[n][x][y] = b[4] + b[0] + y + (b[1] % 2 != f) * (b[2]);
            else
                dp[n][x][y] = -1;
        }
    }
}

void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
    cin>>n;
    for(i = 1; i < n; i++){
        cin>>l>>r;
        v[l].pb(r) , v[r].pb(l);
    }
    for(i = 1; i <= n; i++)
        cin>>a[i];
    dfs(1 , 0);
    if(dp[1][0][0] == -1 && dp[1][0][1] == -1)
        cout<<"impossible";
    else if((dp[1][0][0] != -1 && dp[1][0][1] != -1 && dp[1][0][0] < dp[1][0][1]) || (dp[1][0][1] == -1))
        cout<<dp[1][0][0];
    else
        cout<<dp[1][0][1];
}


int main(){
    TL;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
//    cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message (stderr)

xanadu.cpp: In function 'void solve()':
xanadu.cpp:61:12: warning: unused variable 'q' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
xanadu.cpp:61:20: warning: unused variable 'j' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                    ^
xanadu.cpp:61:30: warning: unused variable 'x' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                              ^
xanadu.cpp:61:34: warning: unused variable 'y' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                  ^
xanadu.cpp:61:38: warning: unused variable 's' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
xanadu.cpp:61:46: warning: unused variable 'f' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                              ^
xanadu.cpp:61:50: warning: unused variable 'k' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                  ^
xanadu.cpp:61:54: warning: unused variable 'm' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                      ^
xanadu.cpp:61:58: warning: unused variable 'mn' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~
xanadu.cpp:61:69: warning: unused variable 'mx' [-Wunused-variable]
   61 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~

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