oj.uz

Submission #999122

# Submission time Handle Problem Language Result Execution time Memory
999122 2024-06-15T06:59: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;
      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:188:11: warning: unused variable 'rr' [-Wunused-variable]
  188 |       int rr = -1;
      |           ^~
Main.cpp:209:11: warning: unused variable 'rr' [-Wunused-variable]
  209 |       int rr = -1;
      |           ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 51792 KB Output is correct
2 Correct 75 ms 51796 KB Output is correct
3 Correct 88 ms 51768 KB Output is correct
4 Correct 85 ms 51792 KB Output is correct
5 Correct 66 ms 47700 KB Output is correct
6 Correct 6 ms 19544 KB Output is correct
7 Correct 5 ms 19544 KB Output is correct
8 Correct 6 ms 19548 KB Output is correct
9 Correct 72 ms 44880 KB Output is correct
10 Correct 79 ms 44884 KB Output is correct
11 Correct 75 ms 44880 KB Output is correct
12 Correct 71 ms 44368 KB Output is correct
13 Correct 68 ms 48724 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 19292 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 3054 ms 50996 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 3072 ms 44808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 51792 KB Output is correct
2 Correct 75 ms 51796 KB Output is correct
3 Correct 88 ms 51768 KB Output is correct
4 Correct 85 ms 51792 KB Output is correct
5 Correct 66 ms 47700 KB Output is correct
6 Correct 6 ms 19544 KB Output is correct
7 Correct 5 ms 19544 KB Output is correct
8 Correct 6 ms 19548 KB Output is correct
9 Correct 72 ms 44880 KB Output is correct
10 Correct 79 ms 44884 KB Output is correct
11 Correct 75 ms 44880 KB Output is correct
12 Correct 71 ms 44368 KB Output is correct
13 Correct 68 ms 48724 KB Output is correct
14 Execution timed out 3057 ms 19292 KB Time limit exceeded
15 Halted 0 ms 0 KB -