QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241313#7608. CliquesUNos_maricones#WA 2ms11620kbC++203.5kb2023-11-06 02:08:302023-11-06 02:08:30

Judging History

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

  • [2023-11-06 02:08:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11620kb
  • [2023-11-06 02:08:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ff   first
#define ss   second
#define pb   push_back

typedef long long  ll;
typedef pair<ll,ll>  pii;

const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;

int fpow (int b, int e) {
  int ans = 1;
  int cur = b;
  for (int i = 0; i < 31; ++i) {
    if (e & (1<<i)) ans = (1ll * ans * cur) % mod;
    cur = (1ll * cur * cur) % mod;
  }
  return ans;
}

int n;
const ll inv2 = fpow(2, mod - 2);

vector <int> g[N];
/// Complexity: O(|N|)
/// Tested: https://tinyurl.com/ybdbmbw7(problem L)
int idx; /// top is father of the chain, up is father of a node
vector<int> len, depth, in, out, top, up;
int dfs_len( int u, int p, int d ) {
  up[u] = p;  depth[u] = d;
  int sz = 1;
  for( auto& v : g[u] ) {
    if( v == p ) continue;
    sz += dfs_len(v, u, d+1);
    if(len[ g[u][0] ] <= len[v]) swap(g[u][0], v);
  }
  return len[u] = sz;
}
void dfs_hld( int u, int p = 0 ) {
  in[u] = idx++;
  //narr[ in[u] ] = val[u]; /// to initialize the segment tree
  for( auto& v : g[u] ) {
    if( v == p ) continue;
    top[v] = (v == g[u][0] ? top[u] : v);
    dfs_hld(v, u);
  }
  out[u] = idx-1;
}

int st[8 * N][2], lazy[8 * N][2];

void build_st (int node, int l, int r) {
  lazy[node][0] = lazy[node][1] = 1;
  if (l == r) {
    st[node][0] = 1;
    if (l != 0) st[node][1] = 1;
    return;
  }
  build_st (node * 2, l, (l + r) / 2);
  build_st (node * 2 + 1, (l + r) / 2 + 1, r);
  for (int dim = 0; dim < 2; ++dim)
    st[node][dim] = st[node * 2][dim] + st[node * 2 + 1][dim];
}

void propagate (int node, int dim, int l, int r) {
  st[node][dim] = (1ll * st[node][dim] * fpow(lazy[node][dim], r - l + 1)) % mod;
  lazy[node * 2][dim] = (1ll * lazy[node * 2][dim] * lazy[node][dim]) % mod;
  lazy[node * 2 + 1][dim] = (1ll * lazy[node * 2 + 1][dim] * lazy[node][dim]) % mod;
  lazy[node][dim] = 1;
}

void update (int node, int dim, int l, int r, int a, int b, int p) {
  propagate (node, dim, l, r);
  if (b < l || r < a) return;
  if (a <= l && r <= b) {
    lazy[node][dim] = p;
    propagate (node, dim, l, r);
    return;
  }
  int m = (l + r) / 2;
  update (node * 2, dim, l, m, a, b, p);
  update (node * 2 + 1, dim, m + 1, r, a, b, p);
  st[node][dim] = (st[node * 2][dim] + st[node * 2 + 1][dim]) % mod;
}

void upd_hld( int u, int v, int p ) {
  while( top[u] != top[v] ) {
    if( depth[ top[u] ] < depth[ top[v] ] ) swap(u, v);
    update(1, 0, 0, n, in [ top[u] ], in[ u ], p);
    update(1, 1, 0, n, in [ top[u] ], in[ u ], p);
    u = up[ top[u] ];
  }
  if( depth[u] > depth[v] ) swap(u, v);
  update(1, 0, 0, n, in [ u ], in[ v ], p);
  if (in[ u ] + 1 <= in[v])
    update(1, 1, 0, n, in [ u ] + 1, in[ v ], p);
  return;
}

void build(int root) {
  top = len = in = out = up = depth = vector<int>(n+1);
  idx = 1; /// DS index [1, n]
  dfs_len(root, root, 0);
  top[root] = root;
  dfs_hld(root, root);
  /// initialize DS
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL

  cin >> n;
  for (int i = 0; i + 1 < n; ++i) {
    int u, v; cin >> u >> v;
    u--;v--;
    g[u].pb(v);
    g[v].pb(u);
  }

  build (0);
  build_st(1, 0, n);

  int q; cin >> q;
  for (int i = 0; i < q; ++i) {
    char ty; cin >> ty;
    int u, v; cin >> u >> v;
    u--;v--;
    if (ty == '+') upd_hld (u, v, 2);
    else upd_hld(u, v, inv2);

    cout << (mod + st[1][0] - st[1][1] - 1) % mod << '\n';
  }

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11620kb

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: -100
Wrong Answer
time: 2ms
memory: 10840kb

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:

19
3
11
3
500000004
23
239
2015
239
111
445
4079
32627
255
257
255
223
3011
1027
1283
19
384
4224
7152
721
257
999998152
999996812
999997000
999999560

result:

wrong answer 1st lines differ - expected: '1', found: '19'