Submission #1292912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292912		binminh01	Sumtree (INOI20_sumtree)	C++20	30 / 100	3095 ms	24776 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double
#define sz(a) (int)a.size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define eb emplace_back
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define trav(i, a) for (auto &i: a)

constexpr int mod = (int)1e9 + 7;
constexpr int MX = 500005;
inline int add(int x, const int &y) {x+=y; return x < mod ? x: x - mod;}
inline int sub(int x, const int &y) {x-=y; return x >= 0 ? x: x + mod;}
inline int mul(const int &x, const int &y) {return 1ll*x*y % mod;}
inline int power(int a, int b) {
    int x = 1;
    for (; b; b>>=1) {
        if (b & 1) x = mul(x, a);
        a = mul(a, a);
    }
    return x;
}
int fact[MX], invf[MX];
inline int C(int k, int n) {
    return k >= 0 && k <= n ? mul(fact[n], mul(invf[k], invf[n - k])): 0;
}

int cal(int n, int m) {
    //sum of n non-negative = m
    return C(n - 1, m + n - 1);
}
constexpr int N = 200005;
int n, m, a[N], s[N], t[N], ans;
vi g[N];
void dfs(int u, int p) {
    if (!ans) return;
    s[u] = t[u] = 0;
    trav(v,g[u]) if (v != p) {
        dfs(v, u), s[u]+=s[v], t[u]+=t[v];
        if (~a[u] && s[u] > a[u]) {
            ans = 0;
            return;
        }
    }
    if (~a[u]) {
        ans = mul(ans, cal(t[u] + 1, a[u] - s[u]));
        s[u] = a[u], t[u] = 0;
    } else ++t[u];
}
int main() {
    if (fopen("sumtree.inp", "r")) freopen("sumtree.inp", "r", stdin), freopen("sumtree.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    fact[0] = 1;
    For(i,1,MX) fact[i] = mul(fact[i - 1], i);
    invf[MX - 1] = power(fact[MX - 1], mod - 2);
    Fore(i,MX-2,0) invf[i] = mul(invf[i + 1], i + 1);

    cin >> n >> a[1];
    FOR(i,2,n) a[i] = -1;
    For(i,1,n){
        int u, v; cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    cout << cal(n, a[1]) << '\n';
    int q; cin >> q;
    while (q--) {
        int o, u; cin >> o >> u;
        if (o == 1) cin >> a[u];
        else a[u] = -1;
        ans = 1;
        dfs(1, 0);
        cout << ans << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:43: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     if (fopen("sumtree.inp", "r")) freopen("sumtree.inp", "r", stdin), freopen("sumtree.out", "w", stdout);
      |                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:77:79: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     if (fopen("sumtree.inp", "r")) freopen("sumtree.inp", "r", stdin), freopen("sumtree.out", "w", stdout);
      |                                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30