oj.uz

Submission #999125

# Submission time Handle Problem Language Result Execution time Memory
999125 2024-06-15T07:01:34 Z vjudge1 Sumtree (INOI20_sumtree) C++17
0 / 100
 3000 ms 101204 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";
  for(int i = 1;i<=n;i++) {
    assert(depth[i]*depth[i] <= n*n+10);
  }
  int q;
  cin >> q;
  while(q--) {
    int t;
    cin >> t;
    if(t == 1) {
      int u, v;
      cin >> u >> v;
      val[u] += v; 
      vv[u]=v;
      used[u] = 1;
      int par = up[u][0];
      int rr = -1;
      while(1) {
//        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(1) {
//        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:191:11: warning: unused variable 'rr' [-Wunused-variable]
  191 |       int rr = -1;
      |           ^~
Main.cpp:212:11: warning: unused variable 'rr' [-Wunused-variable]
  212 |       int rr = -1;
      |           ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 131 ms 99924 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 101204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 131 ms 99924 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -