QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #642147 | #7608. Cliques | propane | WA | 0ms | 3628kb | C++20 | 11.3kb | 2024-10-15 10:58:22 | 2024-10-15 10:58:22 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<stdint.h>
#include<algorithm>
using namespace std;
using LL = long long;
// 1_based HLD
// struct Edge{
// int to;
// int w;
// operator int() const { return to; }
// };
using Edge = int;
struct HLD{
int n;
vector<int> sz, top, dep, fa, in, out, seq;
vector<vector<Edge> > g;
int ts;
HLD(const vector<vector<Edge> > &g, int root = 1) : n(int(g.size()) - 1), g(g) {
ts = 0;
sz.resize(n + 1);
top.resize(n + 1);
dep.resize(n + 1);
fa.resize(n + 1);
in.resize(n + 1);
out.resize(n + 1);
seq.resize(n + 1);
dep[root] = 1;
top[root] = root;
dfs_sz(root);
dfs_hld(root);
}
void dfs_sz(int u){
if (fa[u]){
for(auto it = g[u].begin(); it != g[u].end(); it++){
if (*it == fa[u]){
g[u].erase(it);
break;
}
}
}
sz[u] = 1;
for(auto &j : g[u]){
fa[j] = u;
dep[j] = dep[u] + 1;
dfs_sz(j);
sz[u] += sz[j];
if (sz[j] > sz[g[u][0]])
swap(j, g[u][0]);
}
}
void dfs_hld(int u){
in[u] = ++ts;
seq[in[u]] = u;
for (auto j : g[u]){
top[j] = (j == g[u][0] ? top[u] : j);
dfs_hld(j);
}
out[u] = ts;
}
int lca(int u, int v){
while (top[u] != top[v]){
if (dep[top[u]] > dep[top[v]]){
u = fa[top[u]];
}
else{
v = fa[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v){
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
bool in_subtree(int u, int v){
return in[v] <= in[u] && in[u] <= out[v];
}
int jump(int u, int k) {
if (dep[u] < k){
return -1;
}
int d = dep[u] - k;
while (dep[top[u]] > d){
u = fa[top[u]];
}
return seq[in[u] - dep[u] + d];
}
int rooted_lca(int a, int b, int c){
return lca(a, b) ^ lca(b, c) ^ lca(c, a);
}
template<typename Q>
void modify_path(int u, int v, const Q &q, bool edge = false){
while(top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
q(in[top[u]], in[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
q(in[u] + edge, in[v]);
}
template<typename Q>
void modify_subtree(int u, const Q &q){
q(in[u], out[u]);
}
template<typename T, typename Q>
T query_path(int u, int v, const Q &q, bool edge = false){
T ret = T();
while(top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret = q(in[top[u]], in[u]) + ret;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return q(in[u] + edge, in[v]) + ret;
}
template<typename T, typename Q>
T query_subtree(int u, const Q &q){
return q(in[u], out[u]);
}
template<typename T, typename Q, typename F>
T query_path_noncommutative(int u, int v, const Q &q, const F &f, bool edge = false){
T left = T(), right = T();
while(top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(left, right);
left = q(in[top[u]], in[u]) + left;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v), swap(left, right);
return f(left, q(in[u] + edge, in[v]) + right);
}
pair<vector<int>, vector<pair<int, int> > > compress(vector<int> v){
auto cmp = [&](int a, int b) { return in[a] < in[b]; };
sort(v.begin(), v.end(), cmp);
v.erase(unique(v.begin(), v.end()), v.end());
const int k = (int)v.size();
for(int i = 0; i + 1 < k; i++){
v.push_back(lca(v[i], v[i + 1]));
}
sort(v.begin(), v.end(), cmp);
v.erase(unique(v.begin(), v.end()), v.end());
vector<pair<int, int> > edges;
vector<int> stk;
for(auto x : v){
while(!stk.empty() && out[stk.back()] < in[x]){
stk.pop_back();
}
if (!stk.empty()){
edges.push_back({stk.back(), x});
}
stk.push_back(x);
}
return {v, edges};
}
};
#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
using namespace std;
template<const int T>
struct ModInt {
const static int mod = T;
int x;
ModInt(int x = 0) : x(x % mod) {}
ModInt(long long x) : x(int(x % mod)) {}
int val() { return x; }
ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
bool operator == (const ModInt &a) const { return x == a.x; };
bool operator != (const ModInt &a) const { return x != a.x; };
void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
void operator /= (const ModInt &a) { *this = *this / a; }
friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}
ModInt pow(int64_t n) const {
ModInt res(1), mul(x);
while(n){
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
ModInt inv() const {
int a = x, b = mod, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
if (u < 0) u += mod;
return u;
}
};
using mint = ModInt<1000000007>;
struct Info{
mint sum = 1;
};
struct Tag{
mint mul = 1;
};
Info operator+(const Info &a, const Info &b){
return {a.sum + b.sum};
}
void apply(Info &x, Tag &a, Tag f){
x.sum *= f.mul;
a.mul *= f.mul;
}
template<class Info, class Tag>
struct LazySegmentTree{
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() {}
LazySegmentTree(int n, Info _init = Info()){
init(vector<Info>(n, _init));
}
LazySegmentTree(const vector<Info> &_init){
init(_init);
}
void init(const vector<Info> &_init){
n = (int)_init.size();
info.assign((n << 2) + 1, Info());
tag.assign((n << 2) + 1, Tag());
function<void(int, int, int)> build = [&](int p, int l, int r){
if (l == r){
info[p] = _init[l - 1];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p){
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v){
::apply(info[p], tag[p], v);
}
void push(int p){
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v){
if (l == r){
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x <= m){
modify(2 * p, l, m, x, v);
}
else{
modify(2 * p + 1, m + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v){
modify(1, 1, n, p, v);
}
Info query(int p, int l, int r, int x, int y){
if (l > y || r < x){
return Info();
}
if (l >= x && r <= y){
return info[p];
}
int m = (l + r) / 2;
push(p);
return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
}
Info query(int l, int r){
return query(1, 1, n, l, r);
}
void modify(int p, int l, int r, int x, int y, const Tag &v){
if (l > y || r < x){
return;
}
if (l >= x && r <= y){
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
modify(2 * p, l, m, x, y, v);
modify(2 * p + 1, m + 1, r, x, y, v);
pull(p);
}
void modify(int l, int r, const Tag &v){
return modify(1, 1, n, l, r, v);
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<vector<int> > g(n + 1);
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
HLD hld(g);
LazySegmentTree<Info, Tag> seg1(n), seg2(n);
const mint inv2 = mint(2).inv();
int m;
cin >> m;
while(m--){
char c; int x, y;
cin >> c >> x >> y;
if (c == '+'){
auto f1 = [&](int l, int r){
seg1.modify(l, r, {2});
};
auto f2 = [&](int l, int r){
seg2.modify(l, r, {2});
};
hld.modify_path(x, y, f1);
int anc = hld.lca(x, y);
if (x != anc){
int t = hld.jump(x, hld.dep[x] - hld.dep[anc] - 1);
hld.modify_path(x, t, f2);
}
if (y != anc){
int t = hld.jump(y, hld.dep[y] - hld.dep[anc] - 1);
hld.modify_path(y, t, f2);
}
}
else{
auto f1 = [&](int l, int r){
seg1.modify(l, r, {inv2});
};
auto f2 = [&](int l, int r){
seg2.modify(l, r, {inv2});
};
hld.modify_path(x, y, f1);
int anc = hld.lca(x, y);
if (x != anc){
int t = hld.jump(x, hld.dep[anc] - hld.dep[x] - 1);
hld.modify_path(x, t, f2);
}
if (y != anc){
int t = hld.jump(y, hld.dep[anc] - hld.dep[y] - 1);
hld.modify_path(y, t, f2);
}
}
cout << seg1.query(1, n).sum - seg2.query(1, n).sum << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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: 3544kb
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 6 250000007 250000011 250000019 250000035 750000023 250000032 55 107 213 500000345 500000347 500000363 500000367 500000711 500001226 500001539 250000740 375000575 875001084 875001986 125001029 125001051 625001171 625000720 625000988 500000522
result:
wrong answer 4th lines differ - expected: '3', found: '6'