QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#223278#7608. Cliquesucup-team484#WA 106ms46748kbC++175.2kb2023-10-21 23:28:212023-10-21 23:28:21

Judging History

你现在查看的是最新测评结果

  • [2023-10-21 23:28:21]
  • 评测
  • 测评结果:WA
  • 用时:106ms
  • 内存:46748kb
  • [2023-10-21 23:28:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef long long ll;
typedef pair<int,int> pii;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
  cout << "{";
  if (sz(v)) print(v[0]);
  for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
  cout << "}\n";
}

const ll MOD = 1e9 + 7;
const int NNN = 1e5;
ll pwp[NNN], pwn[NNN];

ll power(ll a, ll b){
  if(b == 0)
    return 1;
  if(b == 1)
    return a;
  ll x = power(a*a%MOD, b/2);
  return x * (b%2 ? a : 1) % MOD;
}

ll pw(ll e){
  if(e >= 0)
    return pwp[e];
  else
    return pwn[-e];
}

struct segment_tree {
  struct data{
    ll v = 0;
  };
  struct operation{
    ll add = 0;
  };
  static data combine(data dl, data dr){
    //cout << dl.v << " + " << dr.v << endl;
    return {dl.v + dr.v};
  };
  static data calculate(operation o, data d){
    data newd = d;
    (newd.v *= pw(o.add)) %= MOD;
    //cout << d.v << " x " << o.add << " -> " << pw(o.add) << ", " << newd.v << endl;
    return newd;
  };
  static operation merge(operation ot, operation ob){
    operation res = {ot.add + ob.add};
    return res;
  };
  int n, h;
  vector<data> t;
  vector<operation> o;
  segment_tree(int n = 0) : n(n), h(32 - __builtin_clz(n)), t(2 * n), o(n) {}
  segment_tree(vector<data> & a) : segment_tree(a.size()) {
    for (int i = 0; i < n; i++)
      t[i + n] = a[i];
    for (int x = n - 1; x > 0; x--)
      t[x] = combine(t[x << 1], t[x << 1 | 1]);
  }
  void apply(int x, operation op) {
    t[x] = calculate(op, t[x]);
    if (x < n)
      o[x] = merge(op, o[x]);
  }
  void push(int x) {
    for (int s = h; s > 0; s--) {
      int c = x >> s;
      apply(c << 1, o[c]);
      apply(c << 1 | 1, o[c]);
      o[c] = { 0 };
    }
  }
  void build(int x) {
    while (x >>= 1)
      t[x] = calculate(o[x], combine(t[x << 1], t[x << 1 | 1]));
  }
  // set the data at the position i
  void setValue(int i, data d) {
    i += n;
    push(i);
    t[i] = d;
    build(i);
  }
  // query the data on the range [l, r[
  data query(int l, int r) {
    l += n; r += n;
    push(l); push(r - 1);
    data dl = {0}, dr = {0};
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        dl = combine(dl, t[l++]);
      if (r & 1)
        dr = combine(t[--r], dr);
    }
    return combine(dl, dr);
  }
  // apply an operation on the range [l, r[
  void apply(int l, int r, operation op) {
    l += n; r += n;
    push(l); push(r - 1);
    int xl = l, xr = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        apply(l++, op);
      if (r & 1)
        apply(--r, op);
    }
    build(xl); build(xr - 1);
  }
};

struct HLD {
  vector<int> par, depth, root, heavy, pos;
  vector<vector<int>>& e;

  HLD(int n, vector<vector<int>> & e) : e(e), par(n+1), depth(n+1), root(n+1), heavy(n+1), pos(n+1) {
    fill(heavy.begin(), heavy.end(), -1);
    par[1] = -1, depth[1] = 0;
    dfs(1);
    for (int i = 1, cur = 0; i <= n; i++)
      if (par[i] == -1 || heavy[par[i]] != i)
        for (int j = i; j != -1; j = heavy[j])
          root[j] = i, pos[j] = cur++;
  }
  int dfs(int u) {
    int sz = 1, mx = 0;
    for (int v: e[u]) if (v != par[u]) {
      par[v] = u;
      depth[v] = depth[u] + 1;
      int sub = dfs(v);
      if (sub > mx)
        mx = sub, heavy[u] = v;
      sz += sub;
    }
    return sz;
  }
  template<class T> void work(int u, int v, T op) {
    for (; root[u] != root[v]; v = par[root[v]]) {
      if (depth[root[u]] > depth[root[v]])
        swap(u, v);
      op(root[v], pos[root[v]], pos[v]);
    }
    if (depth[u] > depth[v]) swap(u, v);
    op(root[u], pos[u], pos[v]);
  }
  int dist(int u, int v) {
    int ret = -1;
    work(u, v, [this, &ret](int x, int l, int r) { 
      ret += r - l + 1;
    });
    return ret;
  }
};


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<vector<int>> G(N + N-1);
  for(int i=0; i<N-1; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[N+i].push_back(a);
    G[N+i].push_back(b);
    G[a].push_back(N+i);
    G[b].push_back(N+i);
  }
  pwp[0] = pwn[0] = 1;
  pwp[1] = 2;
  pwn[1] = power(2, MOD-2);
  for(int i=2; i<NNN; i++){
    pwp[i] = pwp[i-1] * pwp[1] % MOD;
    pwn[i] = pwn[i-1] * pwn[1] % MOD;
  }

  HLD hld(sz(G), G);
  vector<segment_tree::data> D(N + N-1);
  for(int i=0; i<N; i++){
    D[hld.pos[i]].v = 1;
  }
  for(int i=0; i<N-1; i++){
    D[hld.pos[N+i]].v = -1;
  }
  //for(int i=0; i<N+N-1; i++)
  //  cout << "new pos " << i << " -> " << hld.pos[i] << endl;
  segment_tree S(D);
  int Q;
  cin >> Q;
  auto print_s = [&](){
    for(int i=0; i<N+N-1; i++){
      cout << S.query(i, i+1).v << " ";
    }
    cout << endl;
  };
  //S.apply(0, {1});
  //print_s();
  for(int q=0; q<Q; q++){
    char op;
    int a, b;
    cin >> op >> a >> b;
    a--; b--;
    segment_tree::operation upd_op = { op=='+' ? 1 : -1 } ;
    auto upd_f = [&](int x, int l, int r){
      r++;
      //cout << "upd " << l << " " << r << ": " << upd_op.add << endl;
      S.apply(l, r, upd_op); // TODO exclusive?
    };
    hld.work(a, b, upd_f);
    //print_s();
    ll res = S.query(0, N+N-1).v;
    cout << res-1 << "\n";
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5212kb

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1
3
7
3
7
9

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5196kb

input:

20
8 7
19 10
12 14
3 16
17 13
7 10
5 6
1 9
15 12
5 2
16 13
3 11
20 14
18 6
1 14
16 20
11 10
3 4
20 6
30
+ 10 20
+ 14 20
+ 12 17
- 14 20
- 12 17
+ 4 6
+ 8 20
+ 3 6
- 10 20
+ 2 17
+ 1 16
+ 6 10
+ 9 10
+ 5 15
+ 7 8
- 7 8
+ 2 5
+ 3 18
+ 1 20
+ 8 16
- 3 18
- 5 15
+ 4 20
+ 14 16
- 4 6
+ 8 19
+ 4 7
- 1 16
...

output:

1
3
7
3
1
3
7
15
7
15
31
63
127
255
257
255
259
515
1027
1283
643
385
769
1537
769
785
865
481
737
369

result:

ok 30 lines

Test #3:

score: -100
Wrong Answer
time: 106ms
memory: 46748kb

input:

131072
3641 72511
10338 18718
8949 15478
79108 62887
42154 28540
65359 102645
93744 48493
3277 103211
43542 61315
93315 118634
24021 57937
31034 436
30411 6208
1388 25159
93424 128520
119820 87281
5860 97559
59648 8225
57244 58766
119685 13716
130165 60958
79806 116338
97486 80167
101963 95499
51263...

output:

1
2
4
8
13
27
43
67
119
215
359
423
847
1167
1935
2447
2975
4511
5023
8639
6911
13759
12991
15103
23295
43775
47999
91647
85375
167295
169343
301695
600703
666239
1332351
2664575
2678911
2687103
5374207
5898495
11731455
11731967
22283263
22807551
21955327
43910399
43911423
44207359
44207360
44469504...

result:

wrong answer 78th lines differ - expected: '457443667', found: '1457443674'