oj.uz

Submission #587195

# Submission time Handle Problem Language Result Execution time Memory
587195 2022-07-01T13:10:17 Z keta_tsimakuridze Sumtree (INOI20_sumtree) C++14
10 / 100
 311 ms 73560 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7; // !
int  tmout[N], tmin[N], timer, ans, n, a[N], t_sz[N], t[N];
int p[N][25];
vector<int> V[N];

int fact[2 * N], invfact[2 * N], sz[N];
int pwr(int u, int v) {
    int ans = 1;
    while(v) {
        if(v % 2) ans = ans * u % mod;
        v /= 2;
        u = u * u % mod;
    }
    return ans;
}
int C(int a, int b) {
    if(a < b) return 0;
    return fact[a] * invfact[b] % mod * invfact[a - b] % mod;
}
int sb(int a, int b) {
    return C(a + b - 1, b - 1);
}
void dfs(int u,int P) {
    tmin[u] = ++timer;
    p[u][0] = P;
    for(int i = 1; i < 19; i++) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int i = 0; i < V[u].size(); i++) {
        if(V[u][i] == P) continue;
        dfs(V[u][i], u);
        sz[u] += sz[V[u][i]];
    }
    ++sz[u];
    tmout[u] = timer;
}
/*
void upd_sz(int id, int val) {
    for(id; id >= 1; id -= id & (-id)) t_sz[id] += val;
}
int get_sz(int id) {
    int ans = 0;
    for(id; id <= n; id += id & (-id)) ans += t_sz[id];
    return ans;
}
void upd(int id, int val) {
    for(id; id >= 1; id -= id & (-id)) t[id] += val;
}
int get(int id) {
    int ans = 0;
    for(id; id <= n; id += id & (-id)) ans += t[id];
    return ans;
}
int up(int u) {
    for(int i = 18; i >= 0; i--) {
        // ramdeni mshobelia monishnuli
        if(p[u][i] && get(tmin[p[u][i]]) == get(tmin[u])) u = p[u][i];
    }
    return u;
}
void add(int u, int v) {
    a[u] = v;
    int p = up(u);
    upd(tmout[u], 1); upd(tmin[u] - 1, -1);
    int SZ_p = sz[p] - (get_sz(tmin[p] + 1) - get_sz(tmout[p] + 1));
    int SZ = sz[u] - (get_sz(tmin[u] + 1) - get_sz(tmout[u] + 1));
    upd_sz(tmin[u], -SZ);
    upd_sz(tmin[p], SZ);
    ans = ans * pwr(sb(a[p], SZ_p), mod - 2) % mod * sb(a[p], SZ_p - SZ) % mod * sb(a[u], SZ) % mod;
}
void rem(int u) {
    upd(tmout[u], -1); upd(tmin[u] - 1, 1);
    int p = up(u);
    int SZ = sz[u] - (get_sz(tmin[u] + 1) - get_sz(tmout[u] + 1));
    upd_sz(tmin[u], SZ);
    upd_sz(tmin[p], -SZ);
    int SZ_p = sz[p] - (get_sz(tmin[p] + 1) - get_sz(tmout[p] + 1));


    ans = ans * pwr(sb(a[p], SZ_p - SZ), mod - 2) % mod * pwr(sb(a[u], SZ) , mod - 2) % mod * sb( a[p], SZ_p) % mod;
}*/
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> a[1];
    for(int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        V[u].push_back(v);
        V[v].push_back(u);
    }
    dfs(1, 0);
    fact[0] = invfact[0] = 1;
    for(int i = 1; i <= N + n; i++) {
            fact[i] = fact[i - 1] * i % mod;
            invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod;
    }
    ans = sb(a[1], n);
    cout <<ans << endl;
    int q;
    cin >> q;
    /*
    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int u, v;
            cin >> u >> v;
            add(u, v);
        } else {
            int u;
            cin >> u;
            rem(u);
        }
        cout << ans << endl;
    }*/
 }

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:33:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 71312 KB Output is correct
2 Correct 311 ms 73456 KB Output is correct
3 Correct 272 ms 73424 KB Output is correct
4 Correct 297 ms 73560 KB Output is correct
5 Correct 219 ms 70168 KB Output is correct
6 Correct 48 ms 13016 KB Output is correct
7 Correct 49 ms 12832 KB Output is correct
8 Correct 56 ms 12948 KB Output is correct
9 Correct 256 ms 68904 KB Output is correct
10 Correct 285 ms 68604 KB Output is correct
11 Correct 252 ms 68836 KB Output is correct
12 Correct 270 ms 66080 KB Output is correct
13 Correct 258 ms 67696 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 308 ms 70816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 66804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 71312 KB Output is correct
2 Correct 311 ms 73456 KB Output is correct
3 Correct 272 ms 73424 KB Output is correct
4 Correct 297 ms 73560 KB Output is correct
5 Correct 219 ms 70168 KB Output is correct
6 Correct 48 ms 13016 KB Output is correct
7 Correct 49 ms 12832 KB Output is correct
8 Correct 56 ms 12948 KB Output is correct
9 Correct 256 ms 68904 KB Output is correct
10 Correct 285 ms 68604 KB Output is correct
11 Correct 252 ms 68836 KB Output is correct
12 Correct 270 ms 66080 KB Output is correct
13 Correct 258 ms 67696 KB Output is correct
14 Incorrect 47 ms 11980 KB Output isn't correct
15 Halted 0 ms 0 KB -