QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520992#895. Colorwy2025WA 1ms5584kbC++142.2kb2024-08-15 19:27:402024-08-15 19:27:40

Judging History

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

  • [2024-08-15 19:27:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5584kb
  • [2024-08-15 19:27:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=210,M=4e5+10,inf=1e9;
int n,m,s,t,cnt=-1,h[N*2],now[N*2],dep[N*2],a[N][N],set0[N];
bool vis[N][N];
struct dog{int v,w,nex;}g[M<<1];

void add(int u,int v,int w){g[++cnt]={v,w,h[u]},h[u]=cnt;}

void link(int u,int v,int w){add(u,v,w),add(v,u,0);}

bool bfs(){
	memset(dep,0,sizeof(dep));
	queue<int> q;
	dep[s]=1,q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		now[u]=h[u];
		for(int i=h[u];~i;i=g[i].nex){
			int v=g[i].v,w=g[i].w;
			if(dep[v]||!w) continue;
			dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[t];
}

int dfs(int u,int flow){
	if(u==t||!flow) return flow;
	int hav=flow,x;
	for(int i=now[u];~i&&hav;i=g[i].nex){
		now[u]=i;
		int v=g[i].v,w=g[i].w;
		if(dep[u]+1!=dep[v]||!w) continue;
		x=dfs(v,min(hav,w));
		if(!x) dep[v]=-1;
		g[i].w-=x,g[i^1].w+=x;
		hav-=x;
	}
	return flow-hav;
}

int dinic(){
	int ans=0;
	while(bfs()) ans+=dfs(s,inf);
	return ans;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	if(m%2==0) cout<<"No",exit(0);
	for(int i=1;i<=m;i++) set0[i]=m+2;
	for(int i=1;i<n;i++)
		for(int j=1;j+i<=n;j++)
			cin>>a[i][i+j],a[i+j][i]=a[i][i+j],set0[a[i][i+j]]-=2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[i][a[i][j]]) cout<<"No",exit(0);
			vis[i][a[i][j]]=1;
		}
		for(int j=1;j<=m;j++)
			if(!vis[i][j]) set0[j]-=2;
	}
	for(int i=1;i<=m;i++)
		if(set0[i]<0) cout<<"No",exit(0);
	for(int i=n+1;i<=m+1;i++){
		memset(h,-1,sizeof(h));
		cnt=-1,t=m+i+1;
		for(int j=1;j<=m;j++){
			link(s,j,1);
			for(int k=1;k<i;k++) if(!vis[k][j]) link(j,k+m,1);
			link(j,m+i,set0[j]);
		}
		for(int j=1;j<i;j++) link(j+m,t,1);
		link(i+m,t,m-i+1);
		dinic();
//		cout<<"i="<<i<<"\n";
		for(int j=1;j<=m;j++){
			for(int k=h[j];~k;k=g[k].nex){
				int v=g[k].v,w=g[k].w;
//				assert(w>=0);
				if(!w&&v>m&&v<i+m){
					v-=m;
					a[i][v]=a[v][i]=j;
					vis[i][j]=vis[v][j]=1;
				}
				if(v==m+i&&w!=set0[j]) set0[j]-=2;
			}
		}
	}
	cout<<"Yes\n";
	for(int i=1;i<=m;i++,cout<<"\n")
		for(int j=1;i+j<=m+1;j++) cout<<a[i][i+j]<<" ";
	return 0;
}
/*
3 5
1 2
4

4 5
1 2 3
3 2
1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5
1 2
4

output:

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

result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

9 11
11 10 3 4 7 5 2 8
2 10 7 4 6 5 1
9 6 3 8 4 11
5 11 2 6 7
10 3 9 2
9 8 5
1 10
3

output:

No

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

12 11
2 11 8 9 1 3 10 7 5 4 6
5 11 10 6 4 9 8 7 1 3
3 8 4 9 7 2 10 6 1
5 2 6 1 4 9 10 7
11 2 6 3 1 7 4
7 8 10 3 9 5
5 1 8 11 10
11 4 3 2
6 5 9
2 11
8

output:

Yes
2 11 8 9 1 3 10 7 5 4 6 
5 11 10 6 4 9 8 7 1 3 
3 8 4 9 7 2 10 6 1 
5 2 6 1 4 9 10 7 
11 2 6 3 1 7 4 
7 8 10 3 9 5 
5 1 8 11 10 
11 4 3 2 
6 5 9 
2 11 
8 

result:

ok ok

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 5584kb

input:

3 9
2 8
4

output:

Yes
2 8 9 1 4 5 7 6 0 
4 1 3 9 8 6 0 5 
3 2 1 6 9 5 7 
4 2 6 5 0 8 
5 9 8 7 0 
7 3 8 6 
4 1 2 
2 1 
9 

result:

wrong answer Integer parameter [name=color of edges] equals to 0, violates the range [1, 9]