oj.uz

Submission #999118

# Submission time Handle Problem Language Result Execution time Memory
999118 2024-06-15T06:56:57 Z vjudge1 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 51796 KB 
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
const int N = 4e5+10;
const int MAXNC=5e5+10;
const int LG = 20;
vector<int> g[N];
int tin[N], tout[N], tim=0;
int up[N][LG], val[N];
long long fact[MAXNC];
int depth[N], sz[N], used[N];
/*
namespace BIT {
  int fen[N];
  void add(int at, int vl) {
    at++;
    while(at < N) {
      fen[at] += vl;
      at+=at&(-at);
    }
  }
  int query(int at) {
    at++;
    int res=0;
    while(at) {
      res+=fen[at];
      at-=at&(-at);
    }
    return res;
  }
};
namespace BIT2 {
  int fen[N];
  void add(int at, int vl) {
    at++;
    while(at < N) {
      fen[at] += vl;
      at+=at&(-at);
    }
  }
  int query(int at) {
    at++;
    int res=0;
    while(at) {
      res+=fen[at];
      at-=at&(-at);
    }
    return res;
  }
};
namespace BIT3 {
  int fen[N];
  void add(int at, int vl) {
    at++;
    while(at < N) {
      fen[at] += vl;
      at+=at&(-at);
    }
  }
  int query(int at) {
    at++;
    int res=0;
    while(at) {
      res+=fen[at];
      at-=at&(-at);
    }
    return res;
  }
};
void change(int x, int vl) {
  BIT::add(tin[x], vl);
  BIT::add(tout[x], -vl);
}
int query(int anc, int ch) {
  return BIT::query(tin[ch])-BIT::query(tin[anc]);
}
int query2(int l, int r) {
  if(l>r)return 0;
  if(l == 0)return BIT2::query(r);
  return BIT2::query(r)-BIT2::query(l-1);
}

int query3(int l, int r) {
  if(l>r)return 0;
  if(l == 0)return BIT3::query(r);
  return BIT3::query(r)-BIT3::query(l-1);
}
*/
long long binpow(long long a, long long b) {
  long long res = 1;
  while(b) {
    if(b&1) {
      res=(res*a)%mod;
    }
    a=(a*a)%mod;
    b>>=1;
  }
  return res;
}
long long ncr(long long nn, long long rr) {
  if(rr > nn)return 0;
  if(rr < 0)return 0;
  long long res = fact[nn];
  res = (res*binpow(fact[rr], mod-2))%mod;
  res = (res*binpow(fact[nn-rr], mod-2))%mod;
  return res;
}
void dfs(int at, int p) {
  sz[at]=1;
  up[at][0] = p;
  for(int i = 1;i<LG;i++)up[at][i] = up[up[at][i-1]][i-1];
  tin[at] = tim++;
  for(int to:g[at]) {
    if(to == p)continue;
    depth[to]=depth[at]+1;
    dfs(to, at);
    sz[at]+=sz[to];
  }
  tout[at] = tim++;
}
/*
int findroot(int at) {
  for(int i = LG-1;i>=0;i--) {
    if(up[at][i] != 0 and query(up[at][i], at) == depth[at]-depth[up[at][i]]) {
      at = up[at][i];
    }
  }
  return at;
}
*/
struct ANS {
  long long mult = 1;
  long long zero = 0;
  void add(long long vl) {
    if(vl == 0)
      zero++;
    else
      mult = (mult*vl)%mod;
  }
  void del(long long vl) {
    if(vl == 0) {
      zero--;
    }
    else {
      mult = (mult*binpow(vl, mod-2))%mod;
    }
  }
  long long get() {
    if(zero>0)return 0;
    return mult;
  }

};
int main () {
  cin.tie(0)->sync_with_stdio(0);
  fact[0] = 1;
  for(int i = 1;i<MAXNC;i++)fact[i] = (fact[i-1]*i)%mod;
  int n, r;
  cin >> n >> r;
  for(int i = 1;i<n;i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  int vv[n+1];
  val[1] = r;
  used[1] = 1;
//  for(int i = 2;i<=n;i++)change(i, 1);
//  BIT3::update(tin[1], -n);
//  BIT3::update(tout[1], n);
  ANS ans;
  ans.add(ncr(n+r-1, r));
  cout << ans.get() << "\n";
  int q;
  cin >> q;
  while(q--) {
    int t;
    cin >> t;
    if(t == 1) {
      int u, v;
      cin >> u >> v;
//      int rr = findroot(u);
//      v -= query2(tin[u], tout[u]);
      val[u] += v; 
      vv[u]=v;
//      int szz = query3(tin[u], tout[u]);
      
//      BIT3::update(tin[u], -sz);
//      BIT3::update(tout[u], sz);
      used[u] = 1;
      int par = up[u][0];
      int rr = -1;
      while(par != 0) {
        if(used[par] == 1) {
          ans.del(ncr(sz[par]+val[par]-1, val[par]));
        }
        sz[par] -= sz[u];
        val[par] -= v;
        if(used[par]==1){
          ans.add(ncr(sz[par]+val[par]-1, val[par]));
          break;
        }
      }
      ans.add(ncr(sz[u]+val[u]-1, val[u]));
      
    }
    else {
      int u;
      cin >> u;
      ans.del(ncr(sz[u]+val[u]-1, val[u]));
      used[u] = 0;
      val[u]-=vv[u];
      int par = up[u][0];
      int rr = -1;
      while(par != 0) {
        if(used[par] == 1) {
          ans.del(ncr(sz[par]+val[par]-1, val[par]));
        }
        sz[par] += sz[u];
        val[par] += vv[u];
        if(used[par]==1){
          ans.add(ncr(sz[par]+val[par]-1, val[par]));
          break;
        }
      }
    }
    cout << ans.get() << "\n";
  }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:194:11: warning: unused variable 'rr' [-Wunused-variable]
  194 |       int rr = -1;
      |           ^~
Main.cpp:216:11: warning: unused variable 'rr' [-Wunused-variable]
  216 |       int rr = -1;
      |           ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 51744 KB Output is correct
2 Correct 79 ms 51792 KB Output is correct
3 Correct 75 ms 51796 KB Output is correct
4 Correct 78 ms 51796 KB Output is correct
5 Correct 63 ms 47700 KB Output is correct
6 Correct 6 ms 19544 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 6 ms 19548 KB Output is correct
9 Correct 75 ms 44924 KB Output is correct
10 Correct 69 ms 44752 KB Output is correct
11 Correct 73 ms 44884 KB Output is correct
12 Correct 75 ms 44368 KB Output is correct
13 Correct 69 ms 48716 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 51744 KB Output is correct
2 Correct 79 ms 51792 KB Output is correct
3 Correct 75 ms 51796 KB Output is correct
4 Correct 78 ms 51796 KB Output is correct
5 Correct 63 ms 47700 KB Output is correct
6 Correct 6 ms 19544 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 6 ms 19548 KB Output is correct
9 Correct 75 ms 44924 KB Output is correct
10 Correct 69 ms 44752 KB Output is correct
11 Correct 73 ms 44884 KB Output is correct
12 Correct 75 ms 44368 KB Output is correct
13 Correct 69 ms 48716 KB Output is correct
14 Execution timed out 3050 ms 19288 KB Time limit exceeded
15 Halted 0 ms 0 KB -