QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#221863 | #7608. Cliques | ucup-team1198# | WA | 0ms | 23460kb | C++20 | 4.0kb | 2023-10-21 14:54:31 | 2023-10-21 14:54:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
const int MOD = 1e9 + 7;
int add(int a, int b) {
if (a + b < MOD)
return a + b;
return a + b - MOD;
}
int sub(int a, int b) {
if (a >= b)
return a - b;
return a + MOD - b;
}
int mul(int a, int b) {
return a * 1ll * b % MOD;
}
const int MAXN = 200'200;
vector<int> G[MAXN];
int sz[MAXN];
vector<int> order;
int tin[MAXN];
int par[MAXN];
int path_id[MAXN];
int path_st[MAXN];
int depth[MAXN];
void dfs_sz(int v, int p, int w) {
par[v] = p;
sz[v] = 1;
depth[v] = w;
for (int i = 0; i < G[v].size(); ++i) {
if (G[v][i] == p) {
swap(G[v][i], G[v].back());
G[v].pop_back();
--i;
continue;
}
dfs_sz(G[v][i], v, w + 1);
sz[v] += sz[G[v][i]];
if (sz[G[v][i]] > sz[G[v][0]])
swap(G[v][i], G[v][0]);
}
}
void dfs2(int v) {
tin[v] = order.size();
order.emplace_back(v);
for (int u : G[v]) {
dfs2(u);
}
if (G[v].empty()) {
path_id[v] = v;
path_st[v] = v;
} else {
path_id[v] = path_id[G[v][0]];
path_st[path_id[v]] = v;
}
}
const pair<int, int> NONE(1, 0);
const pair<int, int> MUL2(2, 1);
const pair<int, int> DIV2((MOD + 1) / 2, MOD - (MOD + 1) / 2);
struct SegTree {
int val[(1 << 19) + 228];
pair<int, int> mod[(1 << 19) + 228]; // x -> ax+b
pair<int, int> combine(const pair<int, int>& old, const pair<int, int>& new_m) {
return make_pair(new_m.first, add(mul(new_m.first, old.second), new_m.second));
}
void build(int v, int left, int right) {
mod[v] = NONE;
val[v] = 0;
if (left + 1 == right)
return;
int mid = (left + right) / 2;
build(2 * v + 1, left, mid);
build(2 * v + 2, mid, right);
}
void push(int v, int left, int right) {
if (mod[v] == NONE)
return;
val[v] = add(mul(val[v], mod[v].first), mul(mod[v].second, right - left));
if (left + 1 != right) {
mod[2 * v + 1] = combine(mod[2 * v + 1], mod[v]);
mod[2 * v + 2] = combine(mod[2 * v + 2], mod[v]);
}
mod[v] = NONE;
}
void upd(int v, int left, int right, int x, int y, pair<int, int> d) {
push(v, left, right);
if (y <= left || right <= x)
return;
if (x <= left && right <= y) {
mod[v] = combine(mod[v], d);
push(v, left, right);
return;
}
int mid = (left + right) / 2;
upd(2 * v + 1, left, mid, x, y, d);
upd(2 * v + 2, mid, right, x, y, d);
val[v] = add(val[2 * v + 1], val[2 * v + 2]);
}
};
SegTree tree1;
SegTree tree2;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
G[a - 1].emplace_back(b - 1);
G[b - 1].emplace_back(a - 1);
}
dfs_sz(0, -1, 0);
dfs2(0);
tree1.build(0, 0, n);
tree2.build(0, 0, n);
int q;
cin >> q;
while (q--) {
char c;
int u, v;
cin >> c >> u >> v;
--u;
--v;
pair<int, int> to_upd = c == '+' ? MUL2 : DIV2;
while (path_id[u] != path_id[v]) {
if (depth[path_st[path_id[u]]] < depth[path_st[path_id[v]]])
swap(u, v);
tree1.upd(0, 0, n, tin[path_st[path_id[u]]], tin[u] + 1, to_upd);
tree2.upd(0, 0, n, tin[path_st[path_id[u]]], tin[u] + 1, to_upd);
u = par[path_st[path_id[u]]];
}
if (depth[u] < depth[v])
swap(u, v);
tree1.upd(0, 0, n, tin[v], tin[u] + 1, to_upd);
tree2.upd(0, 0, n, tin[v] + 1, tin[u] + 1, to_upd);
tree1.push(0, 0, n);
tree2.push(0, 0, n);
cout << sub(tree1.val[0], tree2.val[0]) << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 23460kb
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: 0ms
memory: 23392kb
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 8 17 35 71 34 36 34 38 73 225 431 217 139 277 203 102 118 500000149 86 162 500000085
result:
wrong answer 10th lines differ - expected: '15', found: '8'