oj.uz

Submission #935508

# Submission time Handle Problem Language Result Execution time Memory
935508 2024-02-29T08:26:04 Z Mohammadamin__Sh Sumtree (INOI20_sumtree) C++17
30 / 100
 3000 ms 46880 KB 
//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] , ans = 1, sub[maxn] , num[maxn] , sham[maxn];
vector<int> adj[maxn];
int is[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;
}

void Pre(int v = 1 , int p = 0){
    sub[v] = 1;
    for(int u : adj[v]) {
        if(u != p){
            Pre(u , v);
            sub[v] += sub[u];
        }
    }
}

void Dfs(int v , int p){
    int sum = 0;
    for(int u : adj[v]){
        if(u == p) continue;
        Dfs(u , v);
        if(ans == 0) return;
        sum += num[u];
        sham[v] += sham[u];
    }
    if(is[v] != -1){
        if(is[v] < sum) {
            ans = 0;
            return;
        }
        ans = (ans * tarkib(sub[v] - sham[v] - 1 , is[v] - sum + sub[v] - sham[v] - 1)) % MOD;
        int x = ans;
        num[v] = is[v];
        sham[v] = sub[v];
    }
    else num[v] = sum;
}

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;
    memset(is , -1 , sizeof is);

    cin >> n >> r;
    is[1] = r;
    for(int i = 1 ; i <= n-1 ; i++){
        int u , v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    Pre();
    cin >> q;
    while(q--){
        int ty;
        cin >> ty;
        memset(sham , 0 , sizeof sham);
        memset(num , 0 , sizeof num);
        ans = 1;
        Dfs(1 , 0);
        cout << ans << '\n';
        if(ty == 1){
            int v , w;
            cin >> v >> w;
            is[v] = w;
        }
        else{
            int v;
            cin >> v;
            is[v] = -1;
        }
    }
    memset(sham , 0 , sizeof sham);
    memset(num , 0 , sizeof num);
    ans = 1;
    Dfs(1 , 0);
    cout << ans << '\n';
}

Compilation message

Main.cpp: In function 'void Dfs(long long int, long long int)':
Main.cpp:63:13: warning: unused variable 'x' [-Wunused-variable]
   63 |         int x = ans;
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 46672 KB Output is correct
2 Correct 96 ms 46672 KB Output is correct
3 Correct 99 ms 46880 KB Output is correct
4 Correct 102 ms 46684 KB Output is correct
5 Correct 83 ms 41812 KB Output is correct
6 Correct 11 ms 30044 KB Output is correct
7 Correct 10 ms 29788 KB Output is correct
8 Correct 10 ms 29628 KB Output is correct
9 Correct 93 ms 39244 KB Output is correct
10 Correct 86 ms 39108 KB Output is correct
11 Correct 90 ms 38996 KB Output is correct
12 Correct 83 ms 38740 KB Output is correct
13 Correct 103 ms 46120 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29532 KB Output is correct
2 Correct 11 ms 29680 KB Output is correct
3 Correct 22 ms 29532 KB Output is correct
4 Correct 16 ms 29532 KB Output is correct
5 Correct 134 ms 29532 KB Output is correct
6 Correct 293 ms 29828 KB Output is correct
7 Correct 322 ms 29820 KB Output is correct
8 Correct 306 ms 29784 KB Output is correct
9 Correct 525 ms 30032 KB Output is correct
10 Correct 546 ms 29968 KB Output is correct
11 Correct 604 ms 29788 KB Output is correct
12 Correct 54 ms 29904 KB Output is correct
13 Correct 672 ms 30152 KB Output is correct
14 Correct 667 ms 30044 KB Output is correct
15 Correct 755 ms 30120 KB Output is correct
16 Correct 566 ms 29788 KB Output is correct
17 Correct 618 ms 29892 KB Output is correct
18 Correct 530 ms 30052 KB Output is correct
19 Correct 565 ms 30140 KB Output is correct
20 Correct 261 ms 29816 KB Output is correct
21 Correct 251 ms 29812 KB Output is correct
22 Correct 70 ms 29532 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 45916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3012 ms 39504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 46672 KB Output is correct
2 Correct 96 ms 46672 KB Output is correct
3 Correct 99 ms 46880 KB Output is correct
4 Correct 102 ms 46684 KB Output is correct
5 Correct 83 ms 41812 KB Output is correct
6 Correct 11 ms 30044 KB Output is correct
7 Correct 10 ms 29788 KB Output is correct
8 Correct 10 ms 29628 KB Output is correct
9 Correct 93 ms 39244 KB Output is correct
10 Correct 86 ms 39108 KB Output is correct
11 Correct 90 ms 38996 KB Output is correct
12 Correct 83 ms 38740 KB Output is correct
13 Correct 103 ms 46120 KB Output is correct
14 Correct 10 ms 29532 KB Output is correct
15 Correct 11 ms 29680 KB Output is correct
16 Correct 22 ms 29532 KB Output is correct
17 Correct 16 ms 29532 KB Output is correct
18 Correct 134 ms 29532 KB Output is correct
19 Correct 293 ms 29828 KB Output is correct
20 Correct 322 ms 29820 KB Output is correct
21 Correct 306 ms 29784 KB Output is correct
22 Correct 525 ms 30032 KB Output is correct
23 Correct 546 ms 29968 KB Output is correct
24 Correct 604 ms 29788 KB Output is correct
25 Correct 54 ms 29904 KB Output is correct
26 Correct 672 ms 30152 KB Output is correct
27 Correct 667 ms 30044 KB Output is correct
28 Correct 755 ms 30120 KB Output is correct
29 Correct 566 ms 29788 KB Output is correct
30 Correct 618 ms 29892 KB Output is correct
31 Correct 530 ms 30052 KB Output is correct
32 Correct 565 ms 30140 KB Output is correct
33 Correct 261 ms 29816 KB Output is correct
34 Correct 251 ms 29812 KB Output is correct
35 Correct 70 ms 29532 KB Output is correct
36 Execution timed out 3058 ms 45916 KB Time limit exceeded
37 Halted 0 ms 0 KB -