QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#335322 | #895. Color | WhangZjian | WA | 1ms | 4000kb | C++14 | 2.5kb | 2024-02-23 09:31:06 | 2024-02-23 09:31:07 |
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]+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