QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377573#8055. BalancecomldWA 116ms75280kbC++144.8kb2024-04-05 15:25:052024-04-05 15:25:18

Judging History

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

  • [2024-04-05 15:25:18]
  • 评测
  • 测评结果:WA
  • 用时:116ms
  • 内存:75280kb
  • [2024-04-05 15:25:05]
  • 提交

answer

#include<bits/stdc++.h>
#define N 400009
using namespace std;
typedef long long ll;
int low[N],dfn[N];
int head[N],siz[N],f[N],br[N],tot=1,tr1[N],tag[N];
int t,si[N],siz1[N],siz2[N],dp1[N],dp2[N],tr2[N];
vector<int>vec[N],ve1[N],ve2[N];
int num=0,n,m,a[N],b[N],c[N],sum1[N],sum2[N],pos[N];
vector<int>::iterator it1;
map<int,int>mp[N],mp1,mp2;
map<int,int>::iterator it;
struct edge{
	int n,to;
}e[N];
int find(int x){
	return f[x]=f[x]==x?x:find(f[x]);
}
inline void add(int u,int v){
	e[++tot].n=head[u];
	e[tot].to=v;
	head[u]=tot;
}
void add1(int u,int v){
	vec[u].push_back(v);
	vec[v].push_back(u);
}
void tarjan(int u,int edge){
	dfn[u]=low[u]=++t;
	for(int i=head[u];i;i=e[i].n) {
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v])br[i]=br[i^1]=1; 
		}
		else if(i!=(edge^1))low[u]=min(low[u],dfn[v]);
	}
	
}
void dfs(int u,int fa){
	siz1[u]=si[u];
	siz2[u]=1;
	dfn[u]=++dfn[0];	
	pos[dfn[0]]=u;
	for(auto v:vec[u])if(v!=fa){
		dfs(v,u);
		siz1[u]+=siz1[v];
		siz2[u]+=siz2[v];
	}
	if(mp1[siz1[u]]){
		int ok=0;
		int x=mp1[siz1[u]];
		if(x==1){
			ok=1;
		}
		else{
			it1=lower_bound(ve1[x-1].begin(),ve1[x-1].end(),dfn[u]);
			if(it1!=ve1[x-1].end()&&((*it1)<=dfn[u]+siz2[u]-1)) {
				ok=1;
				tr1[u]=pos[*it1];
			}
		}
		if(ok)ve1[x].push_back(dfn[u]),dp1[u]=x;
	}
	if(mp2[siz1[u]]){
		int ok=0;
		int x=mp2[siz1[u]];
		if(x==num){
			ok=1;
		}
		else{
			it1=lower_bound(ve2[x+1].begin(),ve2[x+1].end(),dfn[u]);
			if(it1!=ve2[x+1].end()&&((*it1)<=dfn[u]+siz2[u]-1)) {
				ok=1;
				tr2[u]=pos[*it1];
			}
		}
		if(ok)ve2[x].push_back(dfn[u]),dp2[u]=x;
	}
}
inline void sol1(int x,int y){
	for(int i=y-1;i>=1;--i){
		x=tr1[x];
		tag[x]=i;
	}
}
inline void sol2(int x,int y){
	for(int i=y+1;i<=num;++i){
		x=tr2[x];
		tag[x]=i;
	}
}
void dfs2(int u,int fa){
	if(!tag[u])tag[u]=tag[fa];
	for(auto v:vec[u])if(v!=fa){
		dfs2(v,u);	
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		int u,v; 
		for(int i=1;i<=m;++i) {
			cin>>u>>v;
			add(u,v);
			add(v,u);	
		}
		tarjan(1,0);
		for(int u=1;u<=n;++u)f[u]=u;
		for(int u=1;u<=n;++u) {
			for(int i=head[u];i;i=e[i].n)if(br[i]==0){
				int v=e[i].to;
				int xx=find(u),yy=find(v);
				if(xx!=yy) {
					f[xx]=yy;
				}
			}
		}
		for(int u=1;u<=n;++u)si[find(u)]++;
		for(int u=1;u<=n;++u) {
			for(int i=head[u];i;i=e[i].n)if(br[i]==1){
				int v=e[i].to;
				int xx=find(u),yy=find(v);
				if(mp[xx].find(yy)==mp[xx].end()) {
					mp[xx][yy]=1;
					mp[yy][xx]=1;
					add1(xx,yy);
				}
			}
		}
		for(int i=0;i<=n;++i)dfn[i]=0; 
		for(int i=1;i<=n;++i)cin>>a[i];
		sort(a+1,a+n+1);
		for(int i=1;i<=n;++i){
			if(i==1||a[i]!=a[i-1]){
				++num;
				b[num]=a[i];
				c[num]=1;
			}
			else c[num]++;
		}
		for(int i=1;i<=num;++i){
			sum1[i]=sum1[i-1]+c[i];
			mp1[sum1[i]]=i;
		}
		for(int i=num;i>=1;--i){
			sum2[i]=sum2[i+1]+c[i];
			mp2[sum2[i]]=i;
		}
		dfs(find(1),0);
	//	for(int i=1;i<=n;++i)if(find(i)==i)cout<<dp1[i]<<" ? "<<dp2[i]<<endl;
		int ok=0;
		if(num==1){
			for(int i=1;i<=n;++i)tag[i]=b[1];
			ok=1;
		}
		if(ok==0)
		for(int i=1;i<=n;++i)if(find(i)==i){
			if(dp1[i]==num-1){
				tag[i]=num-1;
				tag[find(1)]=num;
				ok=1;
				sol1(i,num-1);
				break;
			}
			if(dp2[i]==2){
				tag[i]=2;
				tag[find(1)]=1;
				ok=1;
				sol2(i,2);
				break;
			}
		}
		if(ok==0)
		for(int i=1;i<=n;++i)if(find(i)==i){
			if(dp1[i]) {
				int x=dp1[i]+2;
				it1=lower_bound(ve2[x].begin(),ve2[x].end(),dfn[i]+siz2[i]);
				if(it1!=ve2[x].end()){
					int y=pos[*it1];
					tag[find(1)]=x-1;
					tag[i]=dp1[i];
					tag[y]=x;
					ok=1;
					sol1(i,dp1[i]);
					sol2(y,x);
					break;
				}
			}
			if(dp2[i]) {
				int x=dp2[i]-2;
				if(x<0)continue;
				it1=lower_bound(ve1[x].begin(),ve1[x].end(),dfn[i]+siz2[i]);
				if(it1!=ve1[x].end()){
					int y=pos[*it1];
					tag[find(1)]=x+1;
					tag[i]=dp2[i];
					tag[y]=x;
					ok=1;
					sol2(i,dp2[i]);
					sol1(y,x);
				//	cout<<i<<" "<<x<<" "<<(*it1)<<endl;
					break;
				}
			}
		}
		if(ok==0){
			cout<<"No\n";
		}
		else{
			cout<<"Yes\n";
			dfs2(find(1),0);
			for(int i=1;i<=n;++i) {
				cout<<tag[find(i)]<<" ";
			}
			cout<<'\n';
		}
		for(int i=0;i<=n;++i){
			low[i]=dfn[i]=head[i]=siz[i]=f[i]=sum1[i]=sum2[i]=pos[i]=0;
			tot=1;
			tr1[i]=tr2[i]=tag[i]=si[i]=siz1[i]=siz2[i]=dp1[i]=dp2[i]=0;
			vec[i].clear();ve1[i].clear();ve2[i].clear(); 
			mp[i].clear();
		}
		for(int i=0;i<=m*2+2;++i)br[i]=0;
		mp1.clear();mp2.clear();
		t=num=0;
//int head[N],siz[N],f[N],br[N],tot=1,tr1[N],tag[N];
//int t,si[N],siz1[N],siz2[N],dp1[N],dp2[N],tr2[N];
//vector<int>vec[N],ve1[N],ve2[N];
//int num=0,n,m,a[N],b[N],c[N],sum1[N],sum2[N],pos[N];
	}
	 
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 73304kb

input:

5
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 2 2 3
5 6
1 2
1 2
2 3
3 4
4 5
3 5
1 2 1 2 1
2 2
1 2
1 2
1 2

output:

Yes
5 4 3 2 1 
No
Yes
2 3 1 2 2 
Yes
2 2 1 1 1 
No

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 116ms
memory: 75280kb

input:

100000
4 3
4 2
1 3
2 1
2 1 3 2
5 7
2 5
5 3
2 3
5 1
4 3
2 4
4 3
1 3 1 1 2
3 2
2 1
2 3
1 1 1
4 7
3 4
1 4
2 3
4 3
4 2
3 1
4 3
2 3 3 2
4 6
2 4
3 1
1 2
1 2
2 3
4 2
1 1 3 3
4 7
3 2
4 2
1 2
3 4
3 2
2 4
3 4
2 1 1 1
5 5
3 2
1 5
4 5
4 3
2 1
1 2 2 3 2
3 5
2 3
1 3
3 1
3 1
2 1
3 2 3
2 3
2 1
2 1
1 2
1 1
2 3
2 1
1...

output:

Yes
2 2 3 1 
No
Yes
1 1 1 
No
No
Yes
2 1 1 1 
No
No
Yes
1 1 
Yes
1 1 
Yes
1 1 
Yes
1 1 1 1 
No
Yes
1 1 1 1 1 
Yes
1 2 1 1 1 
Yes
1 1 1 
Yes
2 1 
Yes
1 1 1 1 1 
Yes
2 1 
No
Yes
1 1 
Yes
1 1 1 
Yes
1 1 
Yes
1 1 1 1 
Yes
1 1 
Yes
2 2 2 2 2 
Yes
1 1 1 1 1 
Yes
1 1 
Yes
1 2 1 1 
No
Yes
1 1 
No
Yes
1 1 
N...

result:

wrong answer 5-th smallest numbers are not same (test case 15)