Submission #935450

#	Time	Username	Problem	Language	Result	Execution time	Memory
935450		Mohammadamin__Sh	Sumtree (INOI20_sumtree)	C++17	10 / 100	76 ms	25988 KiB

Main

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 5e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18 + 100;

int n , r ,q  , fact[maxn];
vector<int> adj[maxn];

ll Power(ll x , ll y){
    if(y < 0 or x < 0) return 0;
    if(y == 0) return 1;
    ll tmp = Power(x , y/2);
    tmp = 1ll * tmp * tmp % MOD;
    if(y&1) tmp = 1ll * x * tmp % MOD;
    return tmp % MOD;
}

ll tarkib(int x , int y){
    if(x == 0 or x == y) return 1;
    if(x > y) return 0;
    ll zir = fact[x] * fact[y-x] % MOD;
    ll res = 1ll * fact[y] * Power(zir , MOD-2);
    return res%MOD;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);

    fact[0] = 1;
    for(int i = 1 ; i < maxn ; i++) fact[i] = (fact[i-1]*i) % MOD;

    cin >> n >> r;
    for(int i = 1 ; i <= n-1 ; i++){
        int u , v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    cin >> q;
    cout << tarkib(n-1 , r+n-1) << '\n';
    //for(int i = 1 ; i <= q ;i++ ) cout << 1 << '\n';
}

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