QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#533397#6127. Kawa ExamEricQianML 3ms30604kbC++145.3kb2024-08-25 21:56:092024-08-25 21:56:10

Judging History

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

  • [2024-08-25 21:56:10]
  • 评测
  • 测评结果:ML
  • 用时:3ms
  • 内存:30604kb
  • [2024-08-25 21:56:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pa pair<int,int>
#define fi first
#define se second
typedef long long ll;
#define Maxn 200005
inline int rd()
{
    int x=0;
    char ch,t=0;
    while(!isdigit(ch = getchar())) t|=ch=='-';
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return t?-x:x;
}
double StartTime;
int n,m,tot,ans,Time,tp,All;
int dfn[Maxn],low[Maxn],sta[Maxn],bel[Maxn],BELlian[Maxn],lianans[Maxn],a[Maxn];
int hea[Maxn],nex[Maxn<<1],ver[Maxn<<1],num[Maxn<<1];
bool edg[Maxn<<1];
bool ins[Maxn],vis[Maxn];

int OUTput[Maxn];

int uu[Maxn],vv[Maxn];
int cnt[Maxn];
int siz[Maxn],bigson[Maxn];
vector<pa> T[Maxn],hav[Maxn];
vector<int> cur;
map<pa,int> mp;
struct TREE
{
	int tree[Maxn<<2];
	void build(int p,int nl,int nr)
	{
		tree[p]=0;
		if(nl==nr) return;
		int mid=(nl+nr)>>1;
		build(p<<1,nl,mid),build(p<<1|1,mid+1,nr);
	}
	void add(int p,int nl,int nr,int x,int k)
	{
		if(nl==nr) { tree[p]+=k; return; }
		int mid=(nl+nr)>>1;
		if(x<=mid) add(p<<1,nl,mid,x,k);
		else add(p<<1|1,mid+1,nr,x,k);
		tree[p]=max(tree[p<<1],tree[p<<1|1]);
	}
	int query(int p,int nl,int nr,int x)
	{
		if(nl==nr) return tree[p];
		int mid=(nl+nr)>>1;
		if(x<=mid) return query(p<<1,nl,mid,x);
		else return query(p<<1|1,mid+1,nr,x);
	}
};
TREE cntup,cntdown;
inline void add(int x,int y,int d)
	{ ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=false,num[tot]=d; }
void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++Time,sta[++tp]=x,ins[x]=true;
	for(int i=hea[x];i;i=nex[i])
	{
		if(!dfn[ver[i]]) tarjan(ver[i],x),low[x]=min(low[x],low[ver[i]]);
		else if(ins[ver[i]] && ver[i]!=fa) low[x]=min(low[x],dfn[ver[i]]);
		if(low[ver[i]]>dfn[x]) // ???
		{
			edg[i]=edg[i^1]=true;
		}
	}
	if(dfn[x]==low[x])
	{
		do
		{
			x=sta[tp],tp--,ins[x]=false;
		} while (dfn[x]!=low[x]);
	}
}
void dfs1(int x)
{
	vis[x]=true;
	cur.push_back(x);
	cnt[a[x]]++;
	bel[x]=All;
	for(int i=hea[x];i;i=nex[i]) if(!edg[i] && !vis[ver[i]])
		dfs1(ver[i]);
}
void dfs2(int x,int fa,int BEL)
{
	siz[x]=1;
	BELlian[x]=BEL,vis[x]=true;
	for(pa v:hav[x]) cnt[v.first]+=v.second;
	for(pa v:T[x]) if(v.first!=fa)
	{
		dfs2(v.first,x,BEL),siz[x]+=siz[v.first];
		if(siz[v.first]>siz[bigson[x]]) bigson[x]=v.first;
	}
}
void dfs3(int x,int fa)
{
	for(pa v:hav[x])
		lianans[BELlian[x]]=max(lianans[BELlian[x]],cnt[v.first]),
		cnt[v.first]=0;
	for(pa v:T[x]) if(v.first!=fa) dfs3(v.first,x);
}
inline void Erase(int x)
{
	for(pa v:hav[x])
	{
		cntdown.add(1,1,100000,v.first,v.second);
		cntup.add(1,1,100000,v.first,-v.second);
	}
}
inline void Insert(int x)
{
	for(pa v:hav[x])
	{
		cntdown.add(1,1,100000,v.first,-v.second);
		cntup.add(1,1,100000,v.first,v.second);
	}
}
void dfs5(int x,int fa)
{
	for(pa v:hav[x]) cntdown.add(1,1,100000,v.first,v.second);
	for(pa v:T[x]) if(v.first!=fa)
		dfs5(v.first,x);
}
void dfs6(int x,int fa)
{
	for(pa v:hav[x]) cntdown.add(1,1,100000,v.first,-v.second);
	for(pa v:T[x]) if(v.first!=fa)
		dfs6(v.first,x);
}
void dfs4(int x,int fa)
{
	sta[++tp]=x,Insert(x);
	for(pa v:T[x]) if(v.first!=fa) dfs4(v.first,x);
}
void solve(int x,int fa,int From)
{
	vis[x]=true;
	for(pa v:T[x]) if(v.first!=fa && v.first!=bigson[x])
	{
		int Intp=tp;
		solve(v.first,x,v.second);
		while(tp>Intp) Erase(sta[tp]),tp--;
	}
	for(pa v:T[x]) if(v.first==bigson[x]) { solve(bigson[x],x,v.second); break; }
	for(pa v:T[x]) if(v.first!=fa && v.first!=bigson[x]) dfs4(v.first,x);
	sta[++tp]=x,Insert(x);
	if(From!=-1) OUTput[From]=ans-lianans[BELlian[x]]+(cntdown.tree[1]+cntup.tree[1]);
}
int main()
{
    StartTime=clock();
    // freopen("input.in","r",stdin);
    //freopen(".out","w",stdout);
	int Case=rd();
	while(Case--)
	{
		mp.clear();
		n=rd(),m=rd(),tot=1,ans=Time=All=tp=0;
		for(int i=1;i<=n;i++) bel[i]=BELlian[i]=-1,vis[i]=false,bigson[i]=0,T[i].clear(),hav[i].clear();
		for(int i=1;i<=n;i++) hea[i]=dfn[i]=0,T[i].clear(),ins[i]=false,lianans[i]=0;
		for(int i=1;i<=n;i++) a[i]=rd();
		for(int i=1;i<=m;i++)
		{
			uu[i]=rd(),vv[i]=rd();
			if(uu[i]>vv[i]) swap(uu[i],vv[i]);
			if(uu[i]!=vv[i]) add(uu[i],vv[i],i),add(vv[i],uu[i],i);
			OUTput[i]=-1;
		}
		for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
		for(int i=1;i<=m;i++)
		{
			if(mp.count(pa(uu[i],vv[i])))
			{
				int tmp=mp[pa(uu[i],vv[i])];
				edg[tmp*2]=edg[tmp*2+1]=0;
				edg[i*2]=edg[i*2+1]=0;
			}
			mp[pa(uu[i],vv[i])]=i;
		}
		for(int i=1;i<=n;i++) if(!vis[i])
		{
			All++,dfs1(i);
			for(int v:cur) if(cnt[a[v]]) hav[All].push_back(pa(a[v],cnt[a[v]])),cnt[a[v]]=0;
			cur.clear();
		}
		for(int i=1;i<=n;i++)
			for(int j=hea[i];j;j=nex[j]) if(edg[j])
				T[bel[i]].emplace_back(bel[ver[j]],num[j]);
		for(int i=1;i<=n;i++) vis[i]=false;
		for(int i=1;i<=All;i++) if(!vis[i])
			dfs2(i,0,i),dfs3(i,0),ans+=lianans[i];
		for(int i=1;i<=All;i++) vis[i]=false;
		for(int i=1;i<=All;i++) if(!vis[i])
		{
			dfs5(i,0),solve(i,0,-1);
			while(tp) Erase(sta[tp]),tp--;
			dfs6(i,0);
		}
		for(int i=1;i<=m;i++)
		{
			if(OUTput[i]==-1) printf("%d",ans);
			else printf("%d",OUTput[i]);
			if(i!=m) printf(" ");
			else printf("\n");
		}
	}
    //fclose(stdin);
    //fclose(stdout);
#ifdef EricQian
    printf("usetime %.0lf ms\n",clock()-StartTime);
#else
#endif
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 30604kb

input:

3
7 5
1 2 1 2 1 2 1
1 2
1 3
2 4
5 6
5 7
3 3
1 2 3
1 2
1 3
2 3
2 3
12345 54321
1 2
1 2
1 1

output:

6 5 5 5 4
1 1 1
1 1 1

result:

ok 3 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

5557
2 7
79960 79960
2 2
1 1
1 1
2 2
1 1
2 1
1 2
9 8
21881 70740 70740 21881 22458 22458 639 21881 70740
3 3
1 6
5 8
7 5
5 7
2 3
5 1
7 6
6 7
13064 20716 6746 13064 6746 69225
5 5
4 1
4 1
1 6
4 5
3 2
3 2
8 4
45146 14400 45146 45146 14400 72969 14400 45146
8 6
1 3
4 6
8 3
18 13
48132 37949 92338 92338...

output:


result: