QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#219449 | #7608. Cliques | ucup-team1447# | WA | 0ms | 35464kb | C++14 | 6.6kb | 2023-10-19 14:52:16 | 2023-10-19 14:52:16 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 1000000007
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,int b){return a.x==b;}
friend bool operator !=(modint a,int b){return a.x!=b;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,m;
modint pw[maxn],ipw[maxn];
struct info{
modint x;
int c;
};
struct oper{
int x;
void clr(){x=0;}
};
info operator +(info a,info b){
return {a.x+b.x,a.c+b.c};
}
void operator +=(info&a,oper b){
if(b.x>0)a.x*=pw[b.x];
if(b.x<0)a.x*=ipw[-b.x];
}
void operator +=(oper&a,oper b){
a.x+=b.x;
}
info tr[maxn<<2];
oper tag[maxn<<2];
void up(int p){
tr[p]=tr[p<<1]+tr[p<<1|1];
}
void pt(int p,oper v){
tr[p]+=v;
tag[p]+=v;
}
void down(int p){
pt(p<<1,tag[p]);
pt(p<<1|1,tag[p]);
tag[p].clr();
}
void upd(int p,int l,int r,int x,info y){
if(l==r)return tr[p]=y,void();
int mid=l+r>>1; down(p);
if(x<=mid)upd(p<<1,l,mid,x,y);
else upd(p<<1|1,mid+1,r,x,y);
up(p);
}
void mdf(int p,int l,int r,int nl,int nr,oper v){
if(nl>nr)return;
if(l>=nl&&r<=nr)return tr[p]+=v,void();
int mid=l+r>>1; down(p);
if(nl<=mid)mdf(p<<1,l,mid,nl,nr,v);
if(nr>mid)mdf(p<<1|1,mid+1,r,nl,nr,v);
up(p);
}
info ask(int p,int l,int r,int ql,int qr){
if(ql>qr)return {0,0};
if(l>=ql&&r<=qr)return tr[p];
int mid=l+r>>1;
if(qr<=mid)return ask(p<<1,l,mid,ql,qr);
if(ql>mid)return ask(p<<1|1,mid+1,r,ql,qr);
return ask(p<<1,l,mid,ql,qr)+ask(p<<1|1,mid+1,r,ql,qr);
}
vi e[maxn];
map<pii,vi>mp;
int qid[maxn],qu[maxn],qv[maxn],qlca[maxn],qop[maxn],cnt;
vi buc[maxn];
int fa[maxn],son[maxn],sz[maxn],dep[maxn];
int dfn[maxn],out[maxn],top[maxn],que[maxn],idx;
void dfs1(int u){
sz[u]=1;
for(auto v:e[u]){
if(v==fa[u])continue;
fa[v]=u,dep[v]=dep[u]+1,dfs1(v),sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp,dfn[u]=++idx,que[idx]=u;
if(son[u])dfs2(son[u],tp);
for(auto v:e[u])if(v!=fa[u]&&v!=son[u])dfs2(v,v);
out[u]=idx;
}
int lca(int u,int v){
for(;top[u]!=top[v];u=fa[top[u]])if(dep[top[u]]<dep[top[v]])swap(u,v);
return dep[u]<dep[v]?u:v;
}
int kth(int u,int k){
while(k>=dfn[u]-dfn[top[u]]+1&&dfn[u]!=1)
k-=dfn[u]-dfn[top[u]]+1,u=fa[top[u]];
return que[dfn[u]-k];
}
int jump(int u,int v){
for(;top[u]!=top[v];u=fa[top[u]])
if(fa[top[u]]==v)return top[u];
return son[v];
}
struct bit{
vector<int>tr;
int n;
void init(int N){n=N,tr=vector<int>(N+1,0);}
void add(int x,int y){for(;x<=n;x+=x&-x)tr[x]+=y;}
int ask(int x){
int s=0;
for(;x;x^=x&-x)s+=tr[x];
return s;
}
void down(){For(i,1,n)tr[i]+=tr[i^(i&-i)];}
void add(int l,int r,int y){
add(l,y);
add(r+1,-y);
}
}T;
int L[maxn],R[maxn],bid[maxn],bidx;
void add(int x){
int u=qu[x],v=qv[x];
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
int t=top[u];
mdf(1,1,cnt,L[t],R[t],{1});
T.add(dfn[t],out[t],1);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
if(u!=v){
int u2=que[dfn[u]+1];
T.add(dfn[u2],dfn[v],1);
mdf(1,1,cnt,L[u2],R[v],{1});
}
mdf(1,1,cnt,L[u],bid[x]-1,{1});
int c=0;
c+=ask(1,1,cnt,bid[x]+1,R[u]).c;
c+=T.ask(dfn[u]);
// cout<<"C: "<<c<<"\n";
upd(1,1,cnt,bid[x],{pw[c],1});
}
void del(int x){
int u=qu[x],v=qv[x];
upd(1,1,cnt,bid[x],{0,0});
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
int t=top[u];
mdf(1,1,cnt,L[t],R[t],{-1});
T.add(dfn[t],out[t],-1);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
if(u!=v){
int u2=que[dfn[u]+1];
T.add(dfn[u2],dfn[v],-1);
mdf(1,1,cnt,L[u2],R[v],{-1});
}
mdf(1,1,cnt,L[u],bid[x]-1,{-1});
}
signed main()
{
n=read();
pw[0]=ipw[0]=1;
For(i,1,200000)pw[i]=pw[i-1]*2,ipw[i]=ipw[i-1]*((mod+1)/2);
For(i,2,n){
int u=read(),v=read();
e[u].pb(v),e[v].pb(u);
}
dfs1(1);
dfs2(1,1);
m=read();
For(i,1,m){
char ch;
while((ch=getchar())!='+' && ch!='-')ch=getchar();
int u=read(),v=read();
if(u>v)swap(u,v);
if(ch=='+'){
++cnt;
qop[i]=1;
qu[cnt]=u,qv[cnt]=v,qlca[cnt]=lca(u,v);
buc[qlca[cnt]].pb(cnt);
qid[i]=cnt;
mp[mkp(u,v)].pb(cnt);
}else{
int cnt=mp[mkp(u,v)].back();
mp[mkp(u,v)].pop_back();
qid[i]=cnt;
}
}
T.init(n+1);
For(i,1,n){
int u=que[i];
L[u]=bidx+1;
for(int x:buc[u])
bid[x]=++bidx;
R[u]=bidx;
}
For(i,1,m){
if(qop[i]==1) add(qid[i]);
else del(qid[i]);
cout<<tr[1].x.x<<"\n";
}
return 0;
}
/*
5
1 2
5 1
2 3
4 2
3
+ 4 5
+ 2 2
+ 1 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30492kb
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: 35464kb
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 33 67 87 89 87 119 159 287 543 231 195 367 703 352 368 704 500000418 456 242
result:
wrong answer 12th lines differ - expected: '63', found: '33'