QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#423821	#8055. Balance	why081023	WA	117ms	9956kb	C++23	6.4kb	2024-05-28 17:34:40	2024-05-28 17:34:41

Judging History

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

[2024-05-28 17:34:41]
评测

测评结果：WA
用时：117ms
内存：9956kb

查看

[2024-05-28 17:34:40]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
struct node{
	int v,next;
}e[400005];
int h[100005];
vector<int> adj[100005],vis[100005],vis2[100005];
int a[100005];
int dfn[100005],low[100005];
int belong[100005];
int sum[100005];
int tot=1;
int siz[100005];
unordered_set<int>s1,s2;
int f[100005];
int dp[100005][2];
int ans[100005];
int co[100005];
void addedge(int u,int v){
	e[++tot].v=v;
	e[tot].next=h[u];h[u]=tot;
}
stack<int>s;
int tim;
int scc;
void dfs(int u,int go){
	s.push(u);
	//cout<<u<<endl;
	tim++;
	low[u]=dfn[u]=tim;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].v;
		//cout<<v<<" "<<i<<" "<<dfn[v]<<endl;
		if(i==(go^1))continue;
		if(!dfn[v]){
			//cout<<u<<" "<<v<<endl;
			dfs(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]){
				//cout<<"sof";
				scc++;
				while(dfn[s.top()]>=dfn[v]){
					belong[s.top()]=scc;
				//	vis[s.top()]=0;
					sum[scc]++;
					s.pop();
				}
			}
		}
		else low[u]=min(low[u],low[v]);
		//cout<<u<<" "<<v<<" "<<low[u]<<"k"<<dfn[u]<<endl;
	}
}
void dfs2(int u,int fa){
	siz[u]=sum[u];
	//cout<<u<<" "<<sum[u]<<endl;
	f[u]=fa;
	for(int i=0;i<adj[u].size();i++){
		int v=adj[u][i];
		if(v==fa)continue;
		dfs2(v,u);
		siz[u]+=siz[v];
		if(s1.count(siz[v]))vis[u][i]+=1;
		if(s2.count(siz[v]))vis[u][i]+=2;
	}
}
void dfs3(int u,int fa){
	//int Max1,Max2;
	int up=0,down=0;
	for(int i=0;i<adj[u].size();i++){
		int v=adj[u][i];
		if(v==fa)continue;
		dfs3(v,u);
		if(vis[u][i]==1 || vis[u][i]==3)dp[u][0]=max(dp[u][0],dp[v][0]+1);
		else dp[u][0]=max(dp[u][0],dp[v][0]);
		if(vis[u][i]==2 || vis[u][i]==3)dp[u][1]=max(dp[u][1],dp[v][1]+1);
		else dp[u][1]=max(dp[u][1],dp[v][1]); 
		ans[u]=max(ans[u],up+dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
		ans[u]=max(ans[u],down+dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
		up=max(up,dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
		down=max(down,dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
	}
}
void dfs4(int u,int fa,int k){
	co[u]=a[k];
	//cout<<u<<"oo"<<k<<"\n";
	for(int i=0;i<adj[u].size();i++){
		int v=adj[u][i];
		if(v==fa)continue;
		if(u==v)continue;
		if(s1.count(siz[v])&&(dp[v][0]+(vis[u][i]==1 || vis[u][i]==3)==dp[u][0]) &&( vis[u][i]==1 || vis[u][i]==3)){
			//cout<<u<<":"<<v<<endl;
			//cout<<"asfasdfasdfasdfsadf\n";
			//if(vis[u][i]==1 || vis[u][i]==3)vis2[u][i]=1;
			dfs4(v,u,k-1);
			s1.erase(siz[v]);
			continue;
		}
		dfs4(v,u,k);
	}
}
void dfs5(int u,int fa,int k){
	bool flag=0;
	//cout<<u<<" "<<k<<"kk"<<a[k]<<endl;
	co[u]=a[k];
	for(int i=0;i<adj[u].size();i++){
		int v=adj[u][i];
		if(v==fa)continue;
		if(u==v)continue;
		if(s2.count(siz[v])&&(dp[v][1]+(vis[u][i]==2 || vis[u][i]==3)==dp[u][1]) && (vis[u][i]==2 || vis[u][i]==3)){
			//if((vis[u][i]==2 || vis[u][i]==3))vis2[u][i]=2;
			dfs5(v,u,k+1);
			s2.erase(siz[v]);
			continue;
		}
		dfs5(v,u,k);
	}
}
int flag=0;
void dfs6(int u,int fa,int k){
	//cout<<u<<" "<<k<<"kk"<<a[k]<<endl;
	//cout<<u<<" "<<k<<"ooo"<<"\n";
	co[u]=a[k];
	for(int i=0;i<adj[u].size();i++){
		int v=adj[u][i];
		if(v==fa || co[v])continue;
		dfs6(v,u,k);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	/*if(T==100000){
		for(int o=1;o<=498;o++){
			cin>>n>>m;
			for(int i=1;i<=m;i++){
				int u,v;
				cin>>u>>v;
			}
		//	cout<<"sdf"<<endl;
			for(int i=1;i<=n;i++)cin>>a[i];
		}
		cin>>n>>m;
		cout<<n<<" "<<m<<"\n";
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			cout<<u<<" "<<v<<"\n";
		}
		//	cout<<"sdf"<<endl;
		for(int i=1;i<=n;i++)cin>>a[i],cout<<a[i]<<" ";
		return 0;
	}*/
	while(T--){
		for(int i=1;i<=n;i++){
			h[i]=a[i]=dfn[i]=0;
			low[i]=belong[i]=0;
			sum[i]=siz[i]=f[i]=ans[i]=co[i]=dp[i][0]=dp[i][1]=co[i]=0;
			adj[i].clear(),vis[i].clear(),vis2[i].clear();
		}
		tot=1;
		cin>>n>>m;
		while(!s.empty())s.pop();
		s1.clear();
		s2.clear();
		scc=0;
		flag=0;
		tim=0;
		flag=n-1;
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			addedge(u,v);
			addedge(v,u);
		}
	//	cout<<"sdf"<<endl;
		for(int i=1;i<=n;i++)cin>>a[i];
		dfs(1,0);
		scc++;
		while(!s.empty()){
		//	vis[s.top()]=0;
			belong[s.top()]=scc;
			sum[scc]++;
			s.pop();
		}
		//for(int i=1;i<=n;i++)cout<<belong[i]<<" ";
		//cout<<endl;
		for(int u=1;u<=n;u++){
			for(int j=h[u];j;j=e[j].next){
				int v=e[j].v;
				if(belong[u]!=belong[v]){
					//cout<<"sad";
					adj[belong[u]].push_back(belong[v]);
				//	if(belong[u]<belong[v])cout<<belong[u]<<" "<<belong[v]<<"\n";
					vis[belong[u]].push_back(0);
					vis2[belong[u]].push_back(0);
				}
			}
		}
		/*for(int i=1;i<=scc;i++){
			cout<<sum[i]<<" ";
		}
		cout<<endl;*/
		sort(a+1,a+n+1);
		for(int i=2;i<=n;i++){
			if(a[i]!=a[i-1]){
			//	cout<<i-1<<" "<<n-i+1<<endl;
				s1.insert(i-1);
				s2.insert(n-i+1);
			}
			else flag--;
		}
		dfs2(1,0);
		dfs3(1,0);
		int Max=0,pos=0;
		for(int i=1;i<=n;i++){
			if(ans[i]>Max){
				Max=ans[i];
				pos=i;
			}
			//cout<<ans[i]<<endl;
		}
		int gg=unique(a+1,a+n+1)-a-1; 
		if(Max>=flag){
			cout<<"Yes"<<"\n";
		}
		else {
			cout<<"No"<<"\n";
			continue;
		}
		int up=0,down=0;
		int up_pos=0,down_pos=0;
		int anss=0;;
		int aa=0,b=0;
		int t=0;
		int u=pos;
		for(int i=0;i<adj[pos].size();i++){
			int v=adj[pos][i];
			if(v==f[pos])continue;
			anss=max(anss,up+dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
			anss=max(anss,down+dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
		//	cout<<ans<<" "<<flag<<endl;
			if(anss==flag){
				//cout<<"dsaf"<<endl;
				if(anss==up+dp[v][0]+(vis[u][i]==1 || vis[u][i]==3)){
					aa=v,b=up_pos;
					t=dp[v][0]+(vis[u][i]==1 || vis[u][i]==3);
				}
				else {
					b=v;
					aa=down_pos;
					t=down;
				}
				break;
			}
			if(dp[v][1]+(vis[u][i]==2||vis[u][i]==3)>up){
				up=max(up,dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
				up_pos=v;
			}
			if(dp[v][0]+(vis[u][i]==1 || vis[u][i]==3)>down){
				down_pos=v;	
				down=max(down,dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
			}
		}
		//cout<<"asdf"<<endl;
		t++;
		//cout<<pos<<endl;
		//cout<<aa<<" tt"<<b<<" "<<t<<"\n";
		for(int i=0;i<adj[pos].size();i++){
			int v=adj[pos][i];
			if(v==aa)dfs4(aa,pos,t- (vis[u][i]==1 || vis[u][i]==3));
			if(v==b)dfs5(b,pos,t+ (vis[u][i]==2 || vis[u][i]==3));
		}
		//dfs4(a,f[a],t),dfs5(b,f[b],t+2);
		dfs6(1,0,t);
		//for(int i=1;i<=n;i++)cout<<co[i]<<endl;
		for(int i=1;i<=n;i++){
			cout<<co[belong[i]]<<" ";
		}
		cout<<"\n";
	}
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5704kb

input:

output:

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

result:

ok ok (5 test cases)

Test #2:

score: 0

Accepted

time: 80ms

memory: 9956kb

input:

output:

Yes
2 2 1 3 
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 3 1 1 1 
Yes
1 1 1 
Yes
1 2 
Yes
1 1 1 1 1 
Yes
1 2 
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:

ok ok (100000 test cases)

Test #3:

score: -100

Wrong Answer

time: 117ms

memory: 5716kb

input:

83335
9 17
1 4
8 9
5 2
1 3
2 7
1 7
2 8
6 7
2 4
1 8
5 8
7 1
8 6
4 6
4 7
6 9
7 9
7 3 4 4 7 4 2 4 8
6 9
3 1
1 2
3 5
1 2
3 4
4 5
6 3
6 1
6 2
4 3 2 2 1 3
9 8
9 3
5 7
5 9
2 6
1 8
4 1
4 2
4 3
4 2 5 3 4 5 4 5 4
6 7
2 1
1 5
6 1
3 1
6 5
2 4
5 3
2 1 2 1 2 1
4 6
2 1
4 2
1 4
1 2
1 4
3 1
2 2 4 2
6 10
2 3
3 5
2 1
...

output:

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

result:

wrong answer 1-th smallest numbers are not same (test case 993)