QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222126#7608. CliquesPhantomThreshold#WA 3ms27984kbC++202.4kb2023-10-21 15:58:042023-10-21 15:58:04

Judging History

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

  • [2023-10-21 15:58:04]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:27984kb
  • [2023-10-21 15:58:04]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;

const int maxn = 410000;
const int mod  = 1e9+7;
const int inv2 = (mod+1)>>1;

int n;
vector<int>E[maxn];
void addedge(int x,int y)
{
	E[x].push_back(y);E[y].push_back(x);
}

int siz[maxn],son[maxn],fa[maxn],dep[maxn];
void dfs(const int x)
{
	son[x]=0;
	siz[x]=1;
	for(auto y:E[x]) if(y!=fa[x])
	{
		dep[y]=dep[x]+1;
		fa[y]=x;
		dfs(y);
		siz[x]+=siz[y];
		if( siz[son[x]] < siz[y] ) son[x]=y;
	}
}
int top[maxn],dfn[maxn],dfi,idfn[maxn];
void build(const int x,const int tp)
{
	dfn[x]=++dfi; idfn[dfi]=x;
	top[x]=tp;
	if(son[x])
		build(son[x],tp);
	for(auto y:E[x]) if(y!=fa[x] && y!=son[x])
		build(y,y);
}

struct segment
{
	int seg[maxn<<2],flag[maxn<<2];
	void build(const int x,const int l,const int r)
	{
		flag[x]=1;
		if(l==r)
		{
			seg[x]= (idfn[l]>n)?mod-1:1;
			return;
		}
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		build(lc,l,mid); build(rc,mid+1,r);
		seg[x]=(seg[lc]+seg[rc])%mod;
	}
	void pushdown(const int x)
	{
		if(flag[x]!=1)
		{
			int fl=flag[x]; flag[x]=1;
			int lc=x<<1,rc=lc|1;
			seg[lc]=(ll)seg[lc]*fl%mod;
			seg[rc]=(ll)seg[rc]*fl%mod;
			flag[lc]=(ll)flag[lc]*fl%mod;
			flag[rc]=(ll)flag[rc]*fl%mod;
		}
	}
	int lx,rx,c;
	void upd(const int x,const int l,const int r)
	{
		if(rx<l||r<lx) return;
		if(lx<=l&&r<=rx)
		{
			seg[x]=(ll)seg[x]*c%mod;
			flag[x]=(ll)flag[x]*c%mod;
			return;
		}
		pushdown(x);
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		upd(lc,l,mid); upd(rc,mid+1,r);
		seg[x]=(seg[lc]+seg[rc])%mod;
	}
	int query()
	{
		return seg[1];
	}
}seg;
void UPD(int x,int y,int c)
{
	int f1=top[x],f2=top[y];
	while(f1!=f2)
	{
		if(dep[f1]<dep[f2])
		{
			swap(x,y);
			swap(f1,f2);
		}
		seg.lx=dfn[f1],seg.rx=dfn[x],seg.c=c;
		seg.upd(1,1,dfi);
		x=fa[f1],f1=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	seg.lx=dfn[x],seg.rx=dfn[y],seg.c=c;
	seg.upd(1,1,dfi);
}

signed main()
{
	//freopen("tmp.in","r",stdin);
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y; cin>>x>>y;
		addedge(x,n+i);
		addedge(y,n+i);
	}
	
	dep[1]=1; dfs(1);
	dfi=0; build(1,1);
	seg.build(1,1,dfi);
	
	//	cout<<seg.query()-1<<endl;
	int Q; cin>>Q;
	while(Q--)
	{
		string str; cin>>str;
		int x,y; cin>>x>>y;
		if(str[0]=='+') UPD(x,y,2);
		else UPD(x,y,inv2);
		cout<<(seg.query()-1+mod)<<endl;
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 27984kb

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1000000008
1000000010
1000000014
1000000010
1000000014
1000000016

result:

wrong answer 1st lines differ - expected: '1', found: '1000000008'