QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #250140 | #7608. Cliques | arashMLG | WA | 0ms | 26080kb | C++23 | 5.3kb | 2023-11-12 21:45:09 | 2023-11-12 21:45:09 |
Judging History
answer
//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long ll;
#define int long long
const int N = 2e5+7, mod = 1e9+7;
vector<int> g[N];
vector<pair<int,int>> ch[N];
int mark[N], siz[N], h[N], par[N], st[N], up[N], now;
struct dat{int val, lz;} ras[N<<2], yal[N<<2];
int power(int a, int b){
int ans = 1;
while(b){
if (b&1) ans = ans * a % mod;
b /= 2;
a = a * a % mod;
}
return ans;
}
void pre(int v){
mark[v] = 1;
siz[v] = 1;
for(int u : g[v]){
if (mark[u]) continue;
par[u] = v;
h[u] = h[v] + 1;
pre(u);
ch[v].pb({siz[u],u});
siz[v] += siz[u];
}
}
void dfs(int v){
st[v] = ++now;
for(int i=0; i<ll(ch[v].size()); i++){
int u = ch[v][i].S;
up[u] = (i == ll(ch[v].size())-1 ? up[v] : u);
dfs(u);
}
}
void build(int ind, int l, int r){
if (l == r){
ras[ind].val = 1;
yal[ind].val = (l == 1 ? 0 : 1);
ras[ind].lz = yal[ind].lz = 1;
return;
}
int mid = (l+r)>>1;
build(2*ind,l,mid);
build(2*ind+1,mid+1,r);
ras[ind].val = ras[2*ind].val + ras[2*ind+1].val;
ras[ind].lz = 1;
yal[ind].val = yal[2*ind].val + yal[2*ind+1].val;
yal[ind].lz = 1;
}
void shiftras(int ind, int l, int r){
ras[ind].val = ras[ind].val * ras[ind].lz % mod;
if (l != r){
ras[2*ind].lz = ras[2*ind].lz * ras[ind].lz % mod;
ras[2*ind+1].lz = ras[2*ind+1].lz * ras[ind].lz % mod;
}
ras[ind].lz = 1;
}
void updras(int ind, int l, int r, int st, int en, int val){
shiftras(ind,l,r);
if (l > en || st > r) return;
if (l == r || (l >= st && r <= en)){
ras[ind].val = ras[ind].val * val % mod;
if (l != r){
ras[2*ind].lz = ras[2*ind].lz * val % mod;
ras[2*ind+1].lz = ras[2*ind+1].lz * val % mod;
}
return;
}
int mid = (l+r)>>1;
updras(2*ind,l,mid,st,en,val);
updras(2*ind+1,mid+1,r,st,en,val);
ras[ind].val = (ras[2*ind].val + ras[2*ind+1].val) % mod;
}
void shiftyal(int ind, int l, int r){
yal[ind].val = yal[ind].val * yal[ind].lz % mod;
if (l != r){
yal[2*ind].lz = yal[2*ind].lz * yal[ind].lz % mod;
yal[2*ind+1].lz = yal[2*ind+1].lz * yal[ind].lz % mod;
}
yal[ind].lz = 1;
}
void updyal(int ind, int l, int r, int st, int en, int val){
shiftyal(ind,l,r);
if (l > en || st > r) return;
if (l == r || (l >= st && r <= en)){
yal[ind].val = yal[ind].val * val % mod;
if (l != r){
yal[2*ind].lz = yal[2*ind].lz * val % mod;
yal[2*ind+1].lz = yal[2*ind+1].lz * val % mod;
}
return;
}
int mid = (l+r)>>1;
updyal(2*ind,l,mid,st,en,val);
updyal(2*ind+1,mid+1,r,st,en,val);
yal[ind].val = (yal[2*ind].val + yal[2*ind+1].val) % mod;
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
for(int i=1; i<n; i++){
int v,u; cin >> v >> u;
g[v].pb(u);
g[u].pb(v);
}
pre(1);
for(int i=1; i<=n; i++) sort(all(ch[i]));
up[1] = 1;
dfs(1);
build(1,1,n);
int inv = power(2,mod-2);
int q; cin >> q;
while(q--){
char x; cin >> x;
if (x == '+'){
int v,u; cin >> v >> u;
int uu = u, vv = v;
while(up[v] != up[u]){
if (st[up[u]] < st[up[v]]) swap(v,u);
updras(1,1,n,st[up[u]],st[u],2);
u = par[up[u]];
}
if (st[v] > st[u]) swap(v,u);
updras(1,1,n,st[v],st[u],2);
u = uu;
v = vv;
while(up[v] != up[u]){
if (st[up[u]] < st[up[v]]) swap(v,u);
updyal(1,1,n,st[up[u]],st[u],2);
u = par[up[u]];
}
if (st[v] > st[u]) swap(v,u);
if (st[v]+1 <= st[u]) updyal(1,1,n,st[v]+1,st[u],2);
}
else{
int v,u; cin >> v >> u;
int uu = u, vv = v;
while(up[v] != up[u]){
if (st[up[u]] < st[up[v]]) swap(v,u);
updras(1,1,n,st[up[u]],st[u],inv);
u = par[up[u]];
}
if (st[v] > st[u]) swap(v,u);
updras(1,1,n,st[v],st[u],inv);
u = uu;
v = vv;
while(up[v] != up[u]){
if (st[up[u]] < st[up[v]]) swap(v,u);
updyal(1,1,n,st[up[u]],st[u],inv);
u = par[up[u]];
}
if (st[v] > st[u]) swap(v,u);
if (st[v]+1 <= st[u]) updyal(1,1,n,st[v]+1,st[u],inv);
}
cout << (ras[1].val + 2 * mod - yal[1].val - 1) % mod << endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 26080kb
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: 23364kb
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 15 31 63 127 255 257 255 767 1535 2047 2303 1151 639 1279 2559 1279 1295 1375 735 991 495
result:
wrong answer 17th lines differ - expected: '259', found: '767'