Submission #587191

#	Time	Username	Problem	Language	Result	Execution time	Memory
587191		keta_tsimakuridze	Sumtree (INOI20_sumtree)	C++14	0 / 100	473 ms	144232 KiB

Main

#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(){
    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 <= 2 * 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 (stderr)

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: In function 'void upd_sz(long long int, long long int)':
Main.cpp:42:9: warning: statement has no effect [-Wunused-value]
   42 |     for(id; id >= 1; id -= id & (-id)) t_sz[id] += val;
      |         ^~
Main.cpp: In function 'long long int get_sz(long long int)':
Main.cpp:46:9: warning: statement has no effect [-Wunused-value]
   46 |     for(id; id <= n; id += id & (-id)) ans += t_sz[id];
      |         ^~
Main.cpp: In function 'void upd(long long int, long long int)':
Main.cpp:50:9: warning: statement has no effect [-Wunused-value]
   50 |     for(id; id >= 1; id -= id & (-id)) t[id] += val;
      |         ^~
Main.cpp: In function 'long long int get(long long int)':
Main.cpp:54:9: warning: statement has no effect [-Wunused-value]
   54 |     for(id; id <= n; id += id & (-id)) ans += t[id];
      |         ^~
Main.cpp: At global scope:
Main.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main(){
      | ^~~~

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