QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335335#895. ColorWhangZjianRE 50ms4696kbC++142.9kb2024-02-23 09:38:392024-02-23 09:38:39

Judging History

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

  • [2024-02-23 09:38:39]
  • 评测
  • 测评结果:RE
  • 用时:50ms
  • 内存:4696kb
  • [2024-02-23 09:38:39]
  • 提交

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]/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<=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++){
			build(0,i,1);
			for(int j=1;j<=2*((m+1)/2-sz[i][1]-sz[i][2]/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);
			}
		}
		int ans=0;
		while(bfs()){
			ans+=dinic(st,inf);
		}
		//printf("%lld\n",ans);
		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: 0ms
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: 3948kb

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

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

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: 1ms
memory: 3792kb

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: 0
Accepted
time: 1ms
memory: 3800kb

input:

3 9
2 8
4

output:

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


result:

ok ok

Test #6:

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

input:

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

output:

No

result:

ok ok

Test #7:

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

input:

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

output:

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


result:

ok ok

Test #8:

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

input:

2 9
6

output:

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


result:

ok ok

Test #9:

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

input:

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

output:

Yes
2 5 6 1 7 4 3 
7 5 6 4 3 1 
3 2 1 6 4 
4 2 1 7 
3 7 5 
5 6 
2 


result:

ok ok

Test #10:

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

input:

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

output:

Yes
2 4 5 6 1 7 3 
3 4 5 6 1 7 
6 1 7 2 5 
7 2 3 1 
3 4 2 
5 4 
6 


result:

ok ok

Test #11:

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

input:

4 11
1 3 9
9 4
7

output:

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


result:

ok ok

Test #12:

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

input:

1 11

output:

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


result:

ok ok

Test #13:

score: 0
Accepted
time: 50ms
memory: 4696kb

input:

82 199
70 77 112 105 155 100 170 32 185 179 197 164 145 63 166 50 160 30 88 196 2 64 144 42 35 96 27 85 128 44 54 110 175 80 21 154 189 125 86 74 131 106 19 114 18 133 40 13 184 82 89 135 182 117 59 92 137 14 188 20 95 121 183 130 11 46 113 156 153 65 199 56 194 123 52 51 36 49 5 24 34
49 84 77 127 ...

output:

Yes
70 77 112 105 155 100 170 32 185 179 197 164 145 63 166 50 160 30 88 196 2 64 144 42 35 96 27 85 128 44 54 110 175 80 21 154 189 125 86 74 131 106 19 114 18 133 40 13 184 82 89 135 182 117 59 92 137 14 188 20 95 121 183 130 11 46 113 156 153 65 199 56 194 123 52 51 36 49 5 24 34 118 119 111 122 ...

result:

ok ok

Test #14:

score: -100
Runtime Error

input:

72 197
195 140 65 80 45 104 92 126 57 125 157 18 135 117 107 1 172 197 49 142 78 134 52 191 151 181 73 138 150 180 130 93 59 108 188 9 81 51 123 79 178 42 6 17 119 55 118 97 37 22 71 20 36 58 141 165 136 77 30 91 187 190 82 120 129 69 63 2 11 35 19
122 47 62 27 86 74 108 39 107 139 197 117 99 89 180...

output:


result: