oj.uz

Submission #999138

# Submission time Handle Problem Language Result Execution time Memory
999138 2024-06-15T07:18:16 Z vjudge1 Sumtree (INOI20_sumtree) C++17
30 / 100
 3000 ms 44232 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
const int MAXNC = 2*N;
const int mod = 1e9+7;
vector<int> g[N];
long long fact[MAXNC];
int sz[N], tagsm[N];
int tag[N], tmptag[N];
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;
}
long long ans=1;
void dfs(int at, int p) {
  sz[at]=1;
  tagsm[at]=0;
  for(int to:g[at]) {
    if(to == p)continue;
    dfs(to, at);
    sz[at]+=sz[to];
    tagsm[at] += tagsm[to];
  }
  if(tag[at] != -1) {
    long long tmp = tag[at]-tagsm[at];
//    cout << tmp << " " << sz[at] << endl;
    ans=(ans*ncr(sz[at]+tmp-1, tmp))%mod;
    sz[at]=0;
    tagsm[at] = tag[at];
  }

}
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;
  memset(tag, -1, sizeof tag);
  memset(tmptag, -1, sizeof tmptag);
  for(int i = 1;i<n;i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int q;
  cin >> q;
  tag[1] = r;
  dfs(1, 0);
  cout << ans << "\n";
  while(q--) {
    int t;
    cin >> t;
    if(t == 1) {
      int u, v;
      cin >> u >> v;
      tag[u]=v;
    }
    else {
      int u;
      cin >> u;
      tag[u]=-1;
    }
    ans=1;
    dfs(1, 0);
    cout << ans << "\n";
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 44224 KB Output is correct
2 Correct 88 ms 44200 KB Output is correct
3 Correct 85 ms 44220 KB Output is correct
4 Correct 86 ms 44232 KB Output is correct
5 Correct 69 ms 40444 KB Output is correct
6 Correct 10 ms 27996 KB Output is correct
7 Correct 11 ms 27952 KB Output is correct
8 Correct 9 ms 27996 KB Output is correct
9 Correct 82 ms 36692 KB Output is correct
10 Correct 64 ms 36692 KB Output is correct
11 Correct 80 ms 36584 KB Output is correct
12 Correct 62 ms 36180 KB Output is correct
13 Correct 60 ms 43388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 27736 KB Output is correct
2 Correct 9 ms 27652 KB Output is correct
3 Correct 10 ms 27740 KB Output is correct
4 Correct 10 ms 27656 KB Output is correct
5 Correct 40 ms 27884 KB Output is correct
6 Correct 369 ms 27956 KB Output is correct
7 Correct 275 ms 27740 KB Output is correct
8 Correct 277 ms 27960 KB Output is correct
9 Correct 471 ms 28000 KB Output is correct
10 Correct 469 ms 28068 KB Output is correct
11 Correct 476 ms 28076 KB Output is correct
12 Correct 23 ms 28056 KB Output is correct
13 Correct 469 ms 28040 KB Output is correct
14 Correct 468 ms 28024 KB Output is correct
15 Correct 483 ms 28248 KB Output is correct
16 Correct 469 ms 28000 KB Output is correct
17 Correct 471 ms 28032 KB Output is correct
18 Correct 371 ms 27996 KB Output is correct
19 Correct 463 ms 28008 KB Output is correct
20 Correct 214 ms 27736 KB Output is correct
21 Correct 221 ms 27740 KB Output is correct
22 Correct 24 ms 27660 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3094 ms 43528 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 3040 ms 36940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 44224 KB Output is correct
2 Correct 88 ms 44200 KB Output is correct
3 Correct 85 ms 44220 KB Output is correct
4 Correct 86 ms 44232 KB Output is correct
5 Correct 69 ms 40444 KB Output is correct
6 Correct 10 ms 27996 KB Output is correct
7 Correct 11 ms 27952 KB Output is correct
8 Correct 9 ms 27996 KB Output is correct
9 Correct 82 ms 36692 KB Output is correct
10 Correct 64 ms 36692 KB Output is correct
11 Correct 80 ms 36584 KB Output is correct
12 Correct 62 ms 36180 KB Output is correct
13 Correct 60 ms 43388 KB Output is correct
14 Correct 9 ms 27736 KB Output is correct
15 Correct 9 ms 27652 KB Output is correct
16 Correct 10 ms 27740 KB Output is correct
17 Correct 10 ms 27656 KB Output is correct
18 Correct 40 ms 27884 KB Output is correct
19 Correct 369 ms 27956 KB Output is correct
20 Correct 275 ms 27740 KB Output is correct
21 Correct 277 ms 27960 KB Output is correct
22 Correct 471 ms 28000 KB Output is correct
23 Correct 469 ms 28068 KB Output is correct
24 Correct 476 ms 28076 KB Output is correct
25 Correct 23 ms 28056 KB Output is correct
26 Correct 469 ms 28040 KB Output is correct
27 Correct 468 ms 28024 KB Output is correct
28 Correct 483 ms 28248 KB Output is correct
29 Correct 469 ms 28000 KB Output is correct
30 Correct 471 ms 28032 KB Output is correct
31 Correct 371 ms 27996 KB Output is correct
32 Correct 463 ms 28008 KB Output is correct
33 Correct 214 ms 27736 KB Output is correct
34 Correct 221 ms 27740 KB Output is correct
35 Correct 24 ms 27660 KB Output is correct
36 Execution timed out 3094 ms 43528 KB Time limit exceeded
37 Halted 0 ms 0 KB -