QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520800 | #895. Color | do_it_tomorrow | WA | 1ms | 5720kb | C++14 | 3.7kb | 2024-08-15 15:52:26 | 2024-08-15 15:52:28 |
Judging History
answer
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=205;
int n,m,c0[N],c1[N],c2[N],col[N][N],vis[N][N];
struct flow {
static constexpr int inf = 1e9;
static const int maxn = 4e2 + 10, maxm = maxn * maxn + maxn * 2 + 10;
int N, S, T;
int to[maxm * 2], val[maxm * 2], nxt[maxm * 2], fir[maxn], tot;
inline flow(int N_, int S_, int T_) {
N = N_, S = S_, T = T_;
}
inline void clear() {
memset(fir, 0, sizeof(fir));
tot = 1;
}
inline void add(int x, int y, int w, bool f = 1) {
to[++tot] = y, val[tot] = w, nxt[tot] = fir[x], fir[x] = tot;
if (f) add(y, x, 0, 0);
}
int hd[maxn], dep[maxn];
inline bool bfs() {
for (int i = 1; i <= N; i++)
hd[i] = fir[i], dep[i] = -1;
dep[S] = 0;
std::queue<int> Q; Q.push(S);
while (! Q.empty()) {
int u = Q.front(); Q.pop();
if (u == T) return true;
for (int i = hd[u]; i; i = nxt[i])
if (dep[to[i]] == -1 && val[i])
dep[to[i]] = dep[u] + 1, Q.push(to[i]);
}
return false;
}
inline int dfs(int u, int fl) {
if (u == T)
return fl;
int ud = 0;
for (int &i = hd[u]; i; i = nxt[i])
if (dep[u] + 1 == dep[to[i]] && val[i]) {
int k = dfs(to[i], std::min(fl - ud, val[i]));
if (! k) dep[to[i]] = -1;
ud += k, val[i] -= k, val[i ^ 1] += k;
if (ud == fl)
return fl;
}
return ud;
}
inline int Dinic() {
int ans = 0, f;
while (bfs())
while ((f = dfs(S, inf)) > 0)
ans += f;
return ans;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
if(m%2==0){
cout<<"No\n";
return 0;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
cin>>col[i][j];
col[j][i]=col[i][j];
c2[col[i][j]]++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[col[i][j]][i]++){
cout<<"No\n";
return 0;
}
}
for(int j=1;j<=m;j++){
if(!vis[j][i]){
c1[j]++;
}
}
}
for(int i=1;i<=m;i++){
if(c1[i]+c2[i]>(m+1)/2){
cout<<"No\n";
return 0;
}
}
int S=m*2+1,T=S+1;
static flow f(m*2+2,S,T);
while(n<=m){
f.clear();
for(int i=1;i<=m;i++){
f.add(S,i,1);
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(!vis[i][j]){
f.add(i,m+j,1);
}
}
for(int j=1;j<=2*c0[i];j++){
f.add(i,n+m+1,1);
}
}
for(int i=1;i<=n;i++){
f.add(i+m,T,1);
}
for(int i=1;i<=m-n;i++){
f.add(n+m+1,T,1);
}
f.Dinic();
for(int i=1,to;i<=m;i++){
for(int j=f.hd[i];j;j=f.nxt[j]){
if(!f.val[j]){
to=f.to[j];
}
}
if(to<=n+m){
col[to-m][n+1]=i,vis[i][to-m]=vis[i][n+1]=1,c1[i]--;
}
else{
c0[i]--,c1[i]++;
}
}
n++;
}
cout<<"Yes\n";
for(int i=1;i<=m+1;i++){
for(int j=i+1;j<=m+1;j++){
cout<<col[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5608kb
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: 0ms
memory: 3656kb
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: 3640kb
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: 0ms
memory: 5720kb
input:
3 9 2 8 4
output:
Yes 2 8 7 5 9 1 6 0 4 4 8 9 7 6 5 0 0 9 7 6 5 2 3 0 6 5 2 1 4 3 8 3 4 1 2 4 3 2 1 9 7 8 8 7 9
result:
wrong answer Integer parameter [name=color of edges] equals to 0, violates the range [1, 9]