QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#241316 | #7608. Cliques | UNos_maricones# | WA | 2ms | 11928kb | C++20 | 3.5kb | 2023-11-06 02:10:40 | 2023-11-06 02:10:40 |
Judging History
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, 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(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);
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11928kb
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: 11116kb
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'