Submission #1213344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213344		Zero_OP	Star Trek (CEOI20_startrek)	C++20	38 / 100	36 ms	16264 KiB

startrek

#include <bits/stdc++.h>

using namespace std;

//loops (warning : long long)
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r - 1); i >= l; --i)
#define rep(i, l, r) for(int i = (l); i < (r); ++i)

//pairs, tuples
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

//vectors
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

//binary search
#define lwb lower_bound
#define upb upper_bound

//other stuffs
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 1e5 + 5;
const int mod = 1e9 + 7;
template<typename T>
T ext_gcd(T a, T b, T& x, T& y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }

    T x1, y1, d = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

struct mint{
    int v;
    mint() : v(0) {}
    mint(int v) : v(v) {
        if(v < 0) v += mod;
        if(v >= mod) v -= mod;
    }

    friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
    friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }

    mint& operator += (const mint& o){
        v += o.v;
        if(v >= mod) v -= mod;
        return *this;
    }

    mint& operator -= (const mint& o){
        v -= o.v;
        if(v < 0) v += mod;
        return *this;
    }

    mint& operator *= (const mint& o){
        v = 1LL * v * o.v % mod;
        return *this;
    }

    mint power(ll n) const{
        mint result(1), base = *this;
        for(; n > 0; n >>= 1, base *= base){
            if(n & 1) result *= base;
        }
        return result;
    }

    mint inv() const{
        return power(mod - 2);
        //note when mod is non-prime, result = power(\varphi(mod) - 1)
    }

    mint& operator /= (const mint& o){
        return *this *= o.inv();
    }

    friend mint operator - (const mint& a){
        return mint(0) - a;
    }

    friend mint operator + (mint a, const mint& b){ return a += b; }
    friend mint operator - (mint a, const mint& b){ return a -= b; }
    friend mint operator * (mint a, const mint& b){ return a *= b; }
    friend mint operator / (mint a, const mint& b){ return a /= b; }

    friend ostream& operator << (ostream& out, const mint& v){
        return out << v.v;
    }
};

int N; ll D;
bool state[MAX], state_root[MAX], up[MAX];
int cnt[MAX];
vi adj[MAX];
int dp[MAX]; 
//dp[u] = number of nodes can connect nodes that are losing state

void dfs(int u){
    state[u] = false; //losing state if start at subtree u
    for(auto v : adj[u]){
        adj[v].erase(find(all(adj[v]), u));
        dfs(v);
        if(!state[v]) state[u] = 1;
        cnt[u] += !state[v];
    }

    if(state[u] == 0){
        dp[u] = 1;
        for(auto v : adj[u]){
            dp[u] += dp[v];
        }
    } else{
        if(cnt[u] > 1) dp[u] = 0;
        else{
            for(auto v : adj[u]){
                if(!state[v]) dp[u] = dp[v];
            }
        }
    }
}

void reroot_dfs(int u){
    if(adj[u].empty()) return;
    int sum = 0;
    for(int i = 0; i < sz(adj[u]); ++i){
        sum += !state[adj[u][i]];
    }

    for(int i = 0; i < sz(adj[u]); ++i){
        int v = adj[u][i];
        state_root[v] = state[v];
        int state_par = (sum - !state[v] > 0 ? 1 : 0) | up[u];
        up[v] = !state_par;
        if(!state_par) {
            state_root[v] = 1;
        }
        reroot_dfs(v);
    }
}

void testcase(int ntestcase){
    cin >> N >> D;
    for(int i = 1; i < N; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }

    dfs(1);
    up[1] = false;
    reroot_dfs(1);

    state_root[1] = state[1];
    int W = 0, L = 0;
    for(int i = 1; i <= N; ++i){
        W += (state_root[i] == 1);
        L += (state_root[i] == 0);
    }

    int ans = 0;

    if(state[1] == 0){
        ans = 1LL * L * dp[1] % mod;
    } else{
        ans = (1LL * N * N - 1LL * L * dp[1]) % mod;
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int T = 1;
//    cin >> T;
    FOR(i, 0, T) testcase(i);

    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15