oj.uz

Submission #587202

# Submission time Handle Problem Language Result Execution time Memory
587202 2022-07-01T13:29:38 Z keta_tsimakuridze Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 70072 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) {
    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:66: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]
   66 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 67276 KB Output is correct
2 Correct 250 ms 67280 KB Output is correct
3 Correct 289 ms 67220 KB Output is correct
4 Correct 263 ms 67252 KB Output is correct
5 Correct 230 ms 63892 KB Output is correct
6 Correct 50 ms 12932 KB Output is correct
7 Correct 48 ms 12808 KB Output is correct
8 Correct 47 ms 12764 KB Output is correct
9 Correct 247 ms 62608 KB Output is correct
10 Correct 261 ms 62444 KB Output is correct
11 Correct 248 ms 62584 KB Output is correct
12 Correct 267 ms 60116 KB Output is correct
13 Correct 220 ms 62060 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1952 ms 70072 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 3062 ms 64016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 67276 KB Output is correct
2 Correct 250 ms 67280 KB Output is correct
3 Correct 289 ms 67220 KB Output is correct
4 Correct 263 ms 67252 KB Output is correct
5 Correct 230 ms 63892 KB Output is correct
6 Correct 50 ms 12932 KB Output is correct
7 Correct 48 ms 12808 KB Output is correct
8 Correct 47 ms 12764 KB Output is correct
9 Correct 247 ms 62608 KB Output is correct
10 Correct 261 ms 62444 KB Output is correct
11 Correct 248 ms 62584 KB Output is correct
12 Correct 267 ms 60116 KB Output is correct
13 Correct 220 ms 62060 KB Output is correct
14 Incorrect 46 ms 12108 KB Output isn't correct
15 Halted 0 ms 0 KB -