QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#335334 | #895. Color | WhangZjian | RE | 60ms | 4700kb | C++20 | 2.7kb | 2024-02-23 09:38:01 | 2024-02-23 09:38:01 |
Judging History
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: 1ms
memory: 3860kb
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: 3716kb
input:
4 5 1 2 3 3 2 1
output:
No
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3712kb
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: 4028kb
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: 3796kb
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: 1ms
memory: 3716kb
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: 1ms
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: 0ms
memory: 3808kb
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: 3804kb
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: 0ms
memory: 3808kb
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: 3800kb
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: 3816kb
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: 60ms
memory: 4700kb
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...