QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335322#895. ColorWhangZjianWA 1ms4000kbC++142.5kb2024-02-23 09:31:062024-02-23 09:31:07

Judging History

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

  • [2024-02-23 09:31:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4000kb
  • [2024-02-23 09:31:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=221,inf=0x3f3f3f3f;
struct edge{
	int y,inv,nxt,w;
	edge(int y1,int i1,int n1,int w1):y(y1),inv(i1),nxt(n1),w(w1){}
	edge(){}
}e[N*N];
int cnt,st,ed;
int n,m;
int head[3*N],cur[3*N],d[3*N];
int s[N][N];
int sz[N][3];
int vis[N];
void add(int x,int y,int i,int w){
	e[cnt]=edge(y,i,head[x],w);
	head[x]=cnt;
}
void build(int x,int y,int w){
	cnt++;add(x,y,cnt+1,w);
	cnt++;add(y,x,cnt-1,0);
}
int dinic(int x,int flow){
	if(!flow||x==ed) return flow;
	int res=0;
	for(int i=cur[x];~i;i=e[i].nxt,cur[x]=i){
		int y=e[i].y,w=e[i].w;
		if(!w||d[y]!=d[x]+1) continue;
		int tfl=dinic(y,min(flow,w));
		e[i].w-=tfl,e[e[i].inv].w+=tfl;
		flow-=tfl,res+=tfl;
		if(!flow) break;
	}
	return res;
}
bool bfs(){
	queue<int> q;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	for(int i=st;i<=ed;i++) cur[i]=head[i];
	d[st]=1,q.push(st);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];~i;i=e[i].nxt){
			int y=e[i].y,w=e[i].w;
			if(!w||d[y]<inf) continue;
			d[y]=d[x]+1;
			q.push(y);
		}
	}
	return d[ed]!=inf;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=n-i;j++){
		scanf("%d",&s[i][i+j]);
		s[i+j][i]=s[i][i+j];
	}
	if((m+1)&1){
		printf("No");
		return 0;
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		for(int j=1;j<=n;j++){
			if(!s[i][j]) continue;
			if(vis[s[i][j]]){
				printf("No");
				return 0;
			}
			vis[s[i][j]]++;
		}
		for(int j=1;j<=m;j++){
			if(vis[j]) sz[j][2]++;
			else sz[j][1]++;
		}
	}
	for(int i=1;i<=m;i++){
		if(sz[i][2]+sz[i][1]>(m+1)/2){
			printf("No");
			return 0;
		}
	}
	printf("Yes\n");
	for(int x=n+1;x<=m+1;x++){
		memset(head,-1,sizeof(head));
		memset(sz,0,sizeof(sz));
		cnt=0,st=0,ed=n+m+2;
		for(int i=1;i<=m;i++){
			build(0,i,1);
			for(int j=1;j<=2*((m+1)/2-sz[i][1]-sz[i][2]);j++){
				build(i,m+n+1,1);
			}
		}
		for(int i=1;i<=n;i++) build(m+i,ed,1);
		build(m+n+1,ed,m-n);
		for(int i=1;i<=n;i++){
			memset(vis,0,sizeof(vis));
			for(int j=1;j<=n;j++){
				if(!s[i][j]) continue;
				vis[s[i][j]]++;
			}
			for(int j=1;j<=m;j++){
				if(!vis[j]) build(j,m+i,1);
			}
		}
		while(bfs()){
			dinic(st,inf);
		}
		for(int t=1;t<=m;t++){
			for(int i=head[t];~i;i=e[i].nxt){
				if(e[i].y!=st&&e[i].w==0){
					if(e[i].y<=n+m) s[e[i].y-m][x]=s[x][e[i].y-m]=t;
					break;
				}
			}
		}
		n++;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			printf("%d ",s[i][j]);
		}
		printf("\n");
	}
	
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3788kb

input:

3 5
1 2
4

output:

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


result:

ok ok

Test #2:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

score: 0
Accepted
time: 1ms
memory: 3728kb

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: -100
Wrong Answer
time: 0ms
memory: 4000kb

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:

No

result:

wrong answer Jury has the answer but participant has not