oj.uz

답안 #587196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587196 2022-07-01T13:10:49 Z keta_tsimakuridze Sumtree (INOI20_sumtree) C++14
10 / 100
 679 ms 149940 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: 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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 72348 KB Output is correct
2 Correct 321 ms 73380 KB Output is correct
3 Correct 331 ms 73452 KB Output is correct
4 Correct 352 ms 73416 KB Output is correct
5 Correct 249 ms 70100 KB Output is correct
6 Correct 57 ms 13000 KB Output is correct
7 Correct 64 ms 12868 KB Output is correct
8 Correct 69 ms 12856 KB Output is correct
9 Correct 373 ms 69068 KB Output is correct
10 Correct 305 ms 68656 KB Output is correct
11 Correct 330 ms 68880 KB Output is correct
12 Correct 328 ms 66048 KB Output is correct
13 Correct 323 ms 67720 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 12068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 450 ms 149940 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 679 ms 147232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 72348 KB Output is correct
2 Correct 321 ms 73380 KB Output is correct
3 Correct 331 ms 73452 KB Output is correct
4 Correct 352 ms 73416 KB Output is correct
5 Correct 249 ms 70100 KB Output is correct
6 Correct 57 ms 13000 KB Output is correct
7 Correct 64 ms 12868 KB Output is correct
8 Correct 69 ms 12856 KB Output is correct
9 Correct 373 ms 69068 KB Output is correct
10 Correct 305 ms 68656 KB Output is correct
11 Correct 330 ms 68880 KB Output is correct
12 Correct 328 ms 66048 KB Output is correct
13 Correct 323 ms 67720 KB Output is correct
14 Incorrect 53 ms 12068 KB Output isn't correct
15 Halted 0 ms 0 KB -