Submission #587206

#	Time	Username	Problem	Language	Result	Execution time	Memory
587206		keta_tsimakuridze	Sumtree (INOI20_sumtree)	C++14	10 / 100	3054 ms	69876 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][20];
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) {
    if(a[u] != -1) return u;
    return up(p[u][0]);
    for(int i = 18; i >= 0; i--) {
        if(p[u][i] && get(tmin[p[u][i]]) == get(tmin[u])) u = p[u][i];
    }
    return u;
}
int get(int u, int p) {

    int ans = 0;
    for(int i = 0; i < V[u].size(); i++) {
        if(V[u][i] == p) continue;
        if(a[V[u][i]] == -1) ans += get(V[u][i], u);
    }
    return ans + 1;
}
void add(int u, int 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);*/
    int SZ_p = get(p, 0), SZ = get(u, 0);
    a[u] = v;
    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) {
    int save = a[u];
    a[u] = -1;

    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));
    */
    int SZ_p = get(p, 0), SZ = get(u, 0);
  //  cout << SZ_p << "--" << SZ << "??" << a[p] << " " << save<< endl;
    ans = ans * pwr(sb(a[p], SZ_p - SZ), mod - 2) % mod * pwr(sb(save, 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);
        a[i] = -1;
    }
    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 (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(long long int, long long int)':
Main.cpp:51:9: warning: statement has no effect [-Wunused-value]
   51 |     for(id; id >= 1; id -= id & (-id)) t[id] += val;
      |         ^~
Main.cpp: In function 'long long int get(long long int)':
Main.cpp:55:9: warning: statement has no effect [-Wunused-value]
   55 |     for(id; id <= n; id += id & (-id)) ans += t[id];
      |         ^~
Main.cpp: In function 'long long int get(long long int, long long int)':
Main.cpp:69: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]
   69 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main(){
      | ^~~~

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