QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648320#6127. Kawa ExamatgcRE 3ms13848kbC++233.6kb2024-10-17 18:24:362024-10-17 18:24:38

Judging History

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

  • [2024-10-17 18:24:38]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:13848kb
  • [2024-10-17 18:24:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

struct{
	int cnt_v[maxn];
	vector<int>cis[maxn];
	int val,cnt;
	void push(int x){
		cis[++cnt_v[x]].push_back(x);
		if(cnt_v[x]>cnt)cnt=cnt_v[val=x];
	}
	void pop(int x){
		cis[--cnt_v[x]].push_back(x);
		if(val==x){
			while(!cis[cnt].empty()&&cnt_v[cis[cnt].back()]!=cnt)
				cis[cnt].pop_back();
			if(cis[cnt].empty())--cnt;
			else val=cis[cnt].back();
		}
	}
	void clear(){
		for(int i=1;i<=cnt;++i){
			for(int x:cis[i])cnt_v[x]=0;
			// cis[i].swap({});
			// cis[i]={};
			vector<int>().swap(cis[i]);
		}
		val=cnt=0;
	}
}qcommon;

int n,m,va[maxn],fa[maxn];
vector<int>a[maxn],suba[maxn];

struct{int nxt,v;}edge[maxn<<1];
int head[maxn],ec;
void add(int u,int v){edge[++ec]={head[u],v};head[u]=ec;}
int dfn[maxn],low[maxn],dfc,bc,c[maxn],dfu[maxn];
static int s[maxn],tp;
void dfs(int u,int in){
	// infun(u);
	dfu[dfn[s[++tp]=u]=low[u]=++dfc]=u;
	for(int i=head[u];i;i=edge[i].nxt){
		if(i==in)continue;
		int v=edge[i].v;
		if(!dfn[v])dfs(v,i^1),low[u]=min(low[u],low[v]);
		else low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]&&++bc)while(s[tp+1]!=u)a[bc].push_back(va[s[tp]]),c[s[tp--]]=bc;
}

vector<int>G[maxn];
int siz[maxn],son[maxn];
void cal_son(int u,int fa){
	::fa[u]=fa;
	siz[u]=a[u].size();son[u]=0;
	for(int v:G[u])if(v!=fa){
		cal_son(v,u);
		if(siz[son[u]]<siz[v])son[u]=v;
	}
}
int cnt_sub[maxn],cnt_out[maxn];
void dfs_sub(int u,int fa){
	// infun(u,fa,a[u],son[u]);
	for(int v:G[u])if(v!=fa&&v!=son[u]){
		dfs_sub(v,u);qcommon.clear();
	}
	suba[u]=a[u];
	if(son[u]){
		dfs_sub(son[u],u);
		for(int va:a[u])suba[son[u]].push_back(va);
		vector<int>().swap(suba[u]);swap(suba[u],suba[son[u]]);
	}
	// deb(suba[u],a[u]);
	for(int v:a[u])qcommon.push(v);
		// deb(qcommon.cnt);
	for(int v:G[u])if(v!=fa&&v!=son[u])for(int va:suba[v])qcommon.push(va);
	cnt_sub[u]=qcommon.cnt;
	// deb(cnt_sub[u]);
}
void dfs_out(int u,int fa){//when dfs end, push all
	cnt_out[u]=qcommon.cnt;
	// infun(u,fa,cnt_out[u]);
	for(int va:a[u])qcommon.push(va);
	for(int v:G[u])if(v!=fa&&v!=son[u]){
		for(int va:suba[v])qcommon.push(va);
	}
	if(son[u])dfs_out(son[u],u);
	for(int v:G[u])if(v!=fa&&v!=son[u]){
		for(int va:suba[v])qcommon.pop(va);
		dfs_out(v,u);
	}
}
int ans,ansdta[maxn];
void sol(){
	cin>>n>>m;
	#define cls(a) memset(a+1,0,n*sizeof a[0])
	cls(head),cls(dfn),cls(low),cls(c);dfc=bc=ans=0;ec=1;tp=0;
	memset(ansdta+1,0,m*sizeof ansdta[0]);
	for(int i=1;i<=n;++i)cin>>va[i],a[i].clear(),G[i].clear();
	for(int i=1,u,v;i<=m;++i)cin>>u>>v,add(u,v),add(v,u);

	for(int u=1;u<=n;++u)
		if(!dfn[u]){
			int pdfc=dfc;
			int pbc=bc;
			dfs(u,0);
			int CC=0;
			set<pair<int,int>>ES;
			for(int i=pdfc+1;i<=dfc;++i){
				int u=dfu[i];
				for(int i=head[u];i;i=edge[i].nxt)
					if(int v=edge[i].v;c[u]!=c[v]){
						// deb(u,v,c[u],c[v]);
						if(ES.count({c[u],c[v]}))continue;
						ES.insert({c[u],c[v]});
						G[c[u]].push_back(c[v]);

						++CC;
					}
			}
			// deb(dfc,pdfc,CC);
			assert(CC==(bc-pbc-1)*2);

			cal_son(u,0);
			dfs_sub(u,0);qcommon.clear();
			dfs_out(u,0);qcommon.clear();
			int vv=cnt_sub[u];
			ans+=cnt_sub[u];
			for(int i=pdfc+1;i<=dfc;++i){
				int u=dfu[i];
				for(int i=head[u];i;i=edge[i].nxt)
					if(int v=edge[i].v;c[u]!=c[v]) {
						// deb(i,c[u],c[v]);
						if(fa[c[u]]==c[v])ansdta[i>>1]=cnt_out[c[u]]+cnt_sub[c[u]]-vv;
						else ansdta[i>>1]=cnt_out[c[v]]+cnt_sub[c[v]]-vv;
					}
			}
		}
	for(int i=1;i<=m;++i)
		cout<<ans+ansdta[i]<<" \n"[i==m];
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	int T;cin>>T;while(T--)sol();
}

详细

Test #1:

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

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
Runtime Error

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: