QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#219450#7608. Cliquesucup-team1447#WA 6ms20820kbC++146.6kb2023-10-19 14:54:112023-10-19 14:54:12

Judging History

你现在查看的是最新测评结果

  • [2023-10-19 14:54:12]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：20820kb
查看
  • [2023-10-19 14:54:11]
  • 提交

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[u],{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[u],{-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
*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 20820kb

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: 20688kb

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
179
351
687
336
352
688
500000402
440
226

result:

wrong answer 12th lines differ - expected: '63', found: '33'
English 繁體中文 简体中文

服务器时间: 2024-12-05 03:16:53 | 开源项目