oj.uz

Submission #587206

# Submission time Handle Problem Language Result Execution time Memory
587206 2022-07-01T13:33:30 Z keta_tsimakuridze Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 69876 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][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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 65172 KB Output is correct
2 Correct 234 ms 65108 KB Output is correct
3 Correct 277 ms 65108 KB Output is correct
4 Correct 238 ms 65152 KB Output is correct
5 Correct 213 ms 61772 KB Output is correct
6 Correct 48 ms 12904 KB Output is correct
7 Correct 47 ms 12812 KB Output is correct
8 Correct 47 ms 12840 KB Output is correct
9 Correct 233 ms 60760 KB Output is correct
10 Correct 278 ms 60584 KB Output is correct
11 Correct 233 ms 60748 KB Output is correct
12 Correct 224 ms 58768 KB Output is correct
13 Correct 229 ms 60476 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 65172 KB Output is correct
2 Correct 234 ms 65108 KB Output is correct
3 Correct 277 ms 65108 KB Output is correct
4 Correct 238 ms 65152 KB Output is correct
5 Correct 213 ms 61772 KB Output is correct
6 Correct 48 ms 12904 KB Output is correct
7 Correct 47 ms 12812 KB Output is correct
8 Correct 47 ms 12840 KB Output is correct
9 Correct 233 ms 60760 KB Output is correct
10 Correct 278 ms 60584 KB Output is correct
11 Correct 233 ms 60748 KB Output is correct
12 Correct 224 ms 58768 KB Output is correct
13 Correct 229 ms 60476 KB Output is correct
14 Incorrect 46 ms 12004 KB Output isn't correct
15 Halted 0 ms 0 KB -