QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520992 | #895. Color | wy2025 | WA | 1ms | 5584kb | C++14 | 2.2kb | 2024-08-15 19:27:40 | 2024-08-15 19:27:40 |
Judging History
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]