Submission #407005

#	Time	Username	Problem	Language	Result	Execution time	Memory
407005		mat_v	The Xana coup (BOI21_xanadu)	C++14	100 / 100	137 ms	28252 KiB

xanadu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n;
vector<int> graf[100005];
int niz[100005];
bool bio[100005][2][2];
int dp[100005][2][2];

struct s{
    int koji;
    int l1;
    int l2;
};

int resi(int x, int y, int z, int cale){
    ///z - on,y od caleta
    if(bio[x][y][z])return dp[x][y][z];
    bio[x][y][z] = 1;
    dp[x][y][z] = 1e9;
    vector<s> v;
    int trgt = niz[x];
    trgt ^= y; trgt ^= z;
    for(auto c:graf[x]){
        if(c == cale)continue;
        v.pb({c,resi(c,z,0,x),1+resi(c,z,1,x)});
    }
    vector<int>eksli;
    int ans = 0;
    for(auto c:v){
        if(c.l1 > n && c.l2 > n)return dp[x][y][z] = 1e9;
        if(c.l1 > n){
            ans += c.l2;
            trgt ^= 1;
            continue;
        }
        if(c.l2 > n){
            ans += c.l1;
            continue;
        }
        eksli.pb(c.l2 - c.l1);
        ans += c.l1;
    }
    int m = eksli.size();
    if(m == 0){
        if(trgt != 0)return 1e9;
        return dp[x][y][z] = ans;
    }
    int poc = 0;
    if(trgt == 1){
        ans += eksli[0];
        poc = 1;
    }
    ff(i,poc,m - 1){
        if(i + 1 >= m)break;
        if(eksli[i] + eksli[i + 1] < 0)ans += (eksli[i] + eksli[i + 1]);
        else{
            break;
        }
        i++;
    }
    return dp[x][y][z] = ans;
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    ff(i,1,n - 1){
        int a,b;
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
    }
    ff(i,1,n)cin >> niz[i];

    int ans = min(resi(1,0,0,0), resi(1,0,1,0) + 1);
    if(ans > n)cout << "impossible\n";
    else cout << ans << "\n";

    return 0;

}

Compilation message (stderr)

xanadu.cpp: In function 'int resi(int, int, int, int)':
xanadu.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
xanadu.cpp:73:5: note: in expansion of macro 'ff'
   73 |     ff(i,poc,m - 1){
      |     ^~
xanadu.cpp: In function 'int main()':
xanadu.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
xanadu.cpp:90:5: note: in expansion of macro 'ff'
   90 |     ff(i,1,n - 1){
      |     ^~
xanadu.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
xanadu.cpp:96:5: note: in expansion of macro 'ff'
   96 |     ff(i,1,n)cin >> niz[i];
      |     ^~

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