QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241320#7608. CliquesUNos_maricones#WA 2ms10796kbC++203.5kb2023-11-06 02:15:512023-11-06 02:15:52

Judging History

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

  • [2023-11-06 02:15:52]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10796kb
  • [2023-11-06 02:15:51]
  • 提交

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;

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

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

vector <ll> g[N];
/// Complexity: O(|N|)
/// Tested: https://tinyurl.com/ybdbmbw7(problem L)
ll idx; /// top is father of the chain, up is father of a node
vector<ll> len, depth, in, out, top, up;
ll dfs_len( ll u, ll p, ll d ) {
  up[u] = p;  depth[u] = d;
  ll 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( ll u, ll 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;
}

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

void build_st (ll node, ll l, ll 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 (ll dim = 0; dim < 2; ++dim)
    st[node][dim] = st[node * 2][dim] + st[node * 2 + 1][dim];
}

void propagate (ll node, ll dim, ll l, ll 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 (ll node, ll dim, ll l, ll r, ll a, ll b, ll 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;
  }
  ll 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( ll u, ll v, ll p ) {
  while( top[u] != top[v] ) {
    if( depth[ top[u] ] < depth[ top[v] ] ) swap(u, v);
    update(1, 0, 0, n + 5, in [ top[u] ], in[ u ], p);
    update(1, 1, 0, n + 5, in [ top[u] ], in[ u ], p);
    u = up[ top[u] ];
  }
  if( depth[u] > depth[v] ) swap(u, v);
  update(1, 0, 0, n + 5, in [ u ], in[ v ], p);
  if (in[ u ] + 1 <= in[v])
    update(1, 1, 0, n + 5, in [ u ] + 1, in[ v ], p);
  return;
}

void build(ll root) {
  top = len = in = out = up = depth = vector<ll>(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 (ll i = 0; i + 1 < n; ++i) {
    ll u, v; cin >> u >> v;
    u--;v--;
    g[u].pb(v);
    g[v].pb(u);
  }

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

  ll q; cin >> q;
  for (ll i = 0; i < q; ++i) {
    char ty; cin >> ty;
    ll 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: 10796kb

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: 10536kb

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
9
43
9
1
3
7
15
7
15
61
59
235
1047
1049
1047
1063
527
2055
22199
2967
2589
10369
2577
641
1377
1537
867
1249
297

result:

wrong answer 2nd lines differ - expected: '3', found: '9'