Editorial for Bedao Grand Contest 04 - NAND


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>
#include<vector>
using namespace std;

using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define rtn return

#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }

//pairs
#define mp make_pair
#define f first
#define s second

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define cont continue
#define bre break
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define checkp(n) (check[n>>6]&(1<<((n&63)>>1)))
#define set(n)   check[n>>6]|=(1<<((n&63)>>1))
// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s) {
    setIn(s+".inp"); setOut(s+".out");
}
const ll INF = 1e9;
const ll MOD = 1e9+7;
const int Max = 1e5+1;
int n,a[Max];
vi adj[Max];
ll dp[Max][2][2];

int get(int x,int y,int u) {
    int k = x & y;
    if(u == -1) rtn (k == 1 ? 0 : 1);
    else rtn u;
}
void dfs(int u) {
    if(adj[u].empty()) rtn;
    for(auto v : adj[u])  dfs(v);
    int v1 = adj[u][0];
    int v2 = adj[u][1];
    FOR(x1,0,2) {
        FOR(y1,0,2) {
            FOR(x2,0,2) {
                FOR(y2,0,2) {
                    dp[u][get(x1,x2,-1)][get(y1,y2,a[u])] =  (dp[u][get(x1,x2,-1)][get(y1,y2,a[u])] + (ll)dp[v1][x1][y1] * dp[v2][x2][y2]) % MOD;
                    dp[u][get(x1,x2,-1)][get(y1,y2,a[u])] % MOD;
                }
            }
        }
    }
}
void init(){
    cin >> n;
        FOR(i,1,n+1) {
            int x1,x2;
            cin >> x1 >> x2;
            adj[i].pb(x1);
            adj[i].pb(x2);
            cin >> a[i];
        }
}
void build(){
   dp[0][0][0] = dp[0][1][1] = 1;
        dfs(1);
        cout<<((dp[1][0][1] + dp[1][1][0]) % MOD);
}
int main(){
   fastio;
   //setIO("new");
   init();
   build();
   rtn 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.