QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471366 | #895. Color | Rong7 | WA | 1ms | 3836kb | C++14 | 4.0kb | 2024-07-10 20:45:29 | 2024-07-10 20:45:33 |
Judging History
answer
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define inline __inline__ __attribute__ ((always_inline))
namespace io {
int pos;
inline int read (int &p = pos){
static int v; static char c;
v = 1, c = getchar (), p = 0;
while (! isdigit (c)){
if (c == '-')
v = - 1;
c = getchar ();
}
while (isdigit (c)){
p = (p << 1) + (p << 3) + (c - 48);
c = getchar ();
}
return p *= v;
}
inline void write (int x){
if (x < 0)
putchar ('-'), x = - x;
static int sta[65], top;
top = 0;
do {
sta[++ top] = x % 10;
x /= 10;
} while (x);
while (top)
putchar (sta[top --] + 48);
}
inline char next_char (){
static char c;
c = getchar ();
while (c == '\n' || c == ' ' || c == '\r')
c = getchar ();
return c;
}
inline void putss (const string s){
for (int i = 0;i < (int) s.size ();++ i)
putchar (s[i]);
}
};
const int N = 2e2;
int n, m;
int col[N + 5][N + 5];
set < int > rst[N + 5];
namespace Dinic {
const int P = N * 2 + 3, E = N * 10 + 5, inf = 0x3f3f3f3f;
int firs[P + 5], nex[P + 5], to[P + 5], w[P + 5], tot = 1, s, t;
inline void Clear (){
s = t = 0;
for (int i = 1;i <= P;++ i)
firs[i] = 0;
tot = 1;
}
inline void Add (int u, int v, int l){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
w[tot] = l;
++ tot;
nex[tot] = firs[v];
firs[v] = tot;
to[tot] = u;
w[tot] = 0;
}
int dep[P + 5], cur[P + 5];
queue < int > Q;
inline bool Bfs (){
for (int i = 1;i <= t;++ i){
cur[i] = firs[i];
dep[i] = inf;
}
dep[s] = 0;
Q.push (s);
while (! Q.empty ()){
int u = Q.front ();
Q.pop ();
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (w[e] && dep[v] > dep[u] + 1){
dep[v] = dep[u] + 1;
Q.push (v);
}
}
}
return dep[t] != inf;
}
int Dfs (int u, int flow){
if (u == t)
return flow;
int used = 0, rlow;
for (int &e = cur[u], v;e;e = nex[e]){
v = to[e];
if (w[e] && dep[v] == dep[u] + 1){
rlow = Dfs (v, min (w[e], flow - used));
if (rlow){
used += rlow;
w[e] -= rlow;
w[e ^ 1] += rlow;
if (used == flow)
break;
}
}
}
return used;
}
inline int FLOW (){
static int Ansflow; Ansflow = 0;
while (Bfs ())
Ansflow += Dfs (s, inf);
return Ansflow;
}
} using namespace Dinic;
int db[N + 5], oe[N + 5];
signed main (){
io::read (n), io::read (m);
for (int i = 1;i <= m;++ i)
for (int j = 1;j <= m;++ j)
rst[i].insert (j);
if ((m ^ 1) & 1)
return io::putss ("No\n"), 0;
for (int i = 1;i <= n;++ i)
for (int j = i + 1;j <= n;++ j){
io::read (col[i][j]);
if (! rst[i].count (col[i][j]) || ! rst[j].count (col[i][j]))
return io::putss ("No\n"), 0;
rst[i].erase (col[i][j]);
rst[j].erase (col[i][j]);
++ db[col[i][j]];
}
for (int i = 1;i <= n;++ i)
for (int x : rst[i])
++ oe[x];
for (int i = 1;i <= m;++ i)
if (oe[i] + db[i] > m)
return io::putss ("No\n"), 0;
auto lid = [] (const int x){ return x; };
auto rid = [] (const int x){ return x + m; };
while (n <= m){
s = rid (n + 1) + 1, t = s + 1;
for (int i = 1;i <= n;++ i)
for (int x : rst[i])
Add (lid (x), rid (i), 1);
for (int i = 1;i <= m;++ i)
Add (lid (i), rid (n + 1), m + 1 - ((db[i] + oe[i]) << 1)), Add (s, lid (i), 1);
for (int i = 1;i <= n;++ i)
Add (rid (i), t, 1);
Add (rid (n + 1), t, m - n);
if (FLOW () != m)
return io::putss ("No\n"), 0;
for (int i = 1;i <= n;++ i)
for (int e = firs[rid (i)], v;e;e = nex[e]){
v = to[e];
if (w[e] == 1 && v != t)
col[i][n + 1] = v;
}
++ n;
for (int i = 1;i < n;++ i){
rst[i].erase (col[i][n]);
rst[n].erase (col[i][n]);
++ db[col[i][n]], -- oe[col[i][n]];
}
for (int x : rst[n])
++ oe[x];
Clear ();
}
io::putss ("Yes\n");
for (int i = 1;i <= n;++ i, putchar ('\n'))
for (int j = i + 1;j <= n;++ j, putchar (' '))
io::write (col[i][j]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3824kb
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: 3836kb
input:
4 5 1 2 3 3 2 1
output:
No
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
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: 3540kb
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