QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#315214 | #7608. Cliques | thomas_li# | WA | 0ms | 3796kb | C++17 | 3.3kb | 2024-01-27 05:59:24 | 2024-01-27 05:59:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A, class B> void cmx(A& x, B y){ x = max<A>(x,y); }
template<class A, class B> void cmn(A& x, B y){ x = min<A>(x,y); }
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MOD = 1e9+7,i2 = MOD/2+1;
signed main(){
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
struct Seg{
struct Node{
int l,r,sum,lz;
};
vector<Node> seg;
Seg(int n) : seg(4*n+50){build(1,0,n-1);}
void build(int u, int l, int r){
seg[u].l = l; seg[u].r = r;
seg[u].sum = r-l+1;
seg[u].lz = 1;
if(l == r){
return;
}
int mid = (l+r)/2;
build(u*2,l,mid); build(u*2+1,mid+1,r);
}
int query(int u, int l, int r){
if(seg[u].l == l && seg[u].r == r) return seg[u].sum;
push(u);
int mid = (seg[u].l+seg[u].r)/2;
if(r <= mid) return query(u*2,l,r);
else if(l > mid) return query(u*2+1,l,r);
else return (query(u*2,mid,r)+query(u*2+1,mid+1,r))%MOD;
}
int query(int l, int r){
return query(1,l,r);
}
void push(int u){
if(seg[u].lz == 1) return;
for(int v : vi{2*u,2*u+1}){
seg[v].sum = (seg[v].sum*seg[u].lz)%MOD;
seg[v].lz = (seg[v].lz*seg[u].lz)%MOD;
}
seg[u].lz = 1;
}
void upd(int u, int l, int r, int x){
if(seg[u].l == l && seg[u].r == r){
if(x == 0){
seg[u].sum = (seg[u].sum*2)%MOD;
seg[u].lz = (seg[u].lz*2)%MOD;
} else{
seg[u].sum = (seg[u].sum*i2)%MOD;
seg[u].lz = (seg[u].lz*i2)%MOD;
}
return;
}
push(u);
int mid = (seg[u].l+seg[u].r)/2;
if(r <= mid) upd(u*2,l,r,x);
else if(l > mid) upd(u*2+1,l,r,x);
else upd(u*2,l,mid,x),upd(u*2+1,mid+1,r,x);
seg[u].sum = (seg[u*2].sum+seg[u*2+1].sum)%MOD;
}
void upd(int l, int r, int x){
if(l > r) return;
upd(1,l,r,x);
}
};
int n; cin >> n;
vector<vi> adj(n);
vi siz(n),big(n,-1),dep(n),par(n);
rep(i,0,n-1){
int a,b; cin >> a >> b;
a--; b--;
adj[a].PB(b); adj[b].PB(a);
}
auto dfs = [&](auto&& dfs, int u, int p)->void{
siz[u] = 1; par[u] = p;
for(int v : adj[u]) if(v != p){
dep[v] = dep[u]+1;
dfs(dfs,v,u);
siz[u] += siz[v];
if(big[u] == -1 || siz[big[u]] < siz[v]) big[u] = v;
}
};
dfs(dfs,0,-1);
vi top(n),in(n),out(n); int ti = 0;
auto dfs1 = [&](auto&& dfs1, int u, int p, int tp)->void{
top[u] = tp; in[u] = ti++;
if(big[u] != -1) dfs1(dfs1,big[u],u,tp);
for(int v : adj[u]) if(v != p && big[u] != v){
dfs1(dfs1,v,u,v);
}
out[u] = ti-1;
};
dfs1(dfs1,0,-1,0);
Seg st(n),ste(n);
auto add = [&](int u, int v, int x){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u,v);
st.upd(in[top[u]],in[u],x);
ste.upd(in[top[u]]+1,in[u],x);
u = par[top[u]];
}
if(dep[u] > dep[v]) swap(u,v);
st.upd(in[u],in[v],x);
ste.upd(in[u]+1,in[v],x);
};
int q; cin >> q;
while(q--){
char t; int u,v; cin >> t >> u >> v;
u--; v--;
if(t == '+'){
add(u,v,0);
} else{
add(u,v,1);
}
int ans = st.seg[1].sum;
ans = (ans-ste.seg[1].sum+MOD)%MOD;
ans = (ans-2+MOD)%MOD;
cout << ans << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3672kb
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: 3796kb
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:
1000000006 1 7 3 1000000006 3 7 17 9 22 38 78 143 288 290 288 292 581 1093 1349 676 401 787 1555 777 794 876 492 756 380
result:
wrong answer 1st lines differ - expected: '1', found: '1000000006'