QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471410#895. ColorRong7WA 30ms5960kbC++144.1kb2024-07-10 21:00:122024-07-10 21:00:12

Judging History

你现在查看的是最新测评结果

  • [2024-07-10 21:00:12]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:5960kb
  • [2024-07-10 21:00:12]
  • 提交

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 * 4 + 3, E = N * N * 5 + 5, inf = 0x3f3f3f3f;
	int firs[P + 5], nex[E + 5], to[E + 5], w[E + 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 + 1;++ i)
		for (int j = 1;j <= m + 1;++ 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);
		int xxx;
		if ((xxx = FLOW ()) != m){
			if (m == 199)
				printf ("%d %d %d %d\n", n, tot, t, xxx);
			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: 5588kb

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: 3604kb

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3652kb

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: 3636kb

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: 0ms
memory: 3568kb

input:

3 9
2 8
4

output:

Yes
2 8 9 1 4 3 5 6 7 
4 1 3 9 5 6 7 8 
3 2 5 1 7 9 6 
4 6 7 2 8 5 
7 6 8 5 9 
8 1 3 2 
9 2 4 
4 3 
1 


result:

ok ok

Test #6:

score: 0
Accepted
time: 0ms
memory: 3648kb

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: 0ms
memory: 3828kb

input:

5 9
2 7 3 8
6 8 4
2 9
1

output:

Yes
2 7 3 8 9 4 1 6 5 
6 8 4 1 3 9 5 7 
2 9 3 1 5 8 4 
1 4 5 6 7 9 
5 6 7 3 2 
7 8 2 6 
2 9 8 
4 3 
1 


result:

ok ok

Test #8:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

2 9
6

output:

Yes
6 1 2 8 3 9 4 7 5 
2 1 3 9 8 5 4 7 
3 9 8 4 7 5 6 
4 5 7 6 8 9 
7 5 1 6 2 
6 2 1 4 
3 2 1 
9 8 
3 


result:

ok ok

Test #9:

score: 0
Accepted
time: 0ms
memory: 3852kb

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: 3560kb

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: 0ms
memory: 3636kb

input:

4 11
1 3 9
9 4
7

output:

Yes
1 3 9 11 4 7 2 6 5 8 10 
9 4 2 3 11 7 5 6 10 8 
7 4 1 2 6 8 10 5 11 
3 2 6 1 10 8 11 5 
5 8 10 1 7 6 9 
10 8 7 11 9 6 
5 9 3 1 4 
11 9 4 3 
4 3 2 
2 1 
7 


result:

ok ok

Test #12:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

1 11

output:

Yes
1 11 2 10 3 4 5 9 6 8 7 
2 11 3 10 5 4 7 8 6 9 
3 1 4 6 7 8 10 9 5 
4 1 7 6 5 9 10 8 
5 8 9 6 2 7 11 
9 8 2 7 11 6 
3 10 11 1 2 
11 1 2 10 
3 4 1 
5 4 
3 


result:

ok ok

Test #13:

score: -100
Wrong Answer
time: 30ms
memory: 5960kb

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:

172 11191 374 195
No

result:

wrong answer The first line should be "Yes" or "No"