UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198109#3457. 排序程序shiruiheng1001680ms1236kbC++111.8kb2023-11-19 15:15:512023-11-19 16:12:46

answer

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n, m, t, u[1000], v[1000], a[21], b[21], c[21];
string ans[2] = {"NO", "YES"};
bool check() {
	do {
		for(int i = 1 ; i <= n ; i++) {
			b[i] = a[i];
			//cout << b[i] << " \n"[i == n];
		}
		for(int i = 1 ; i <= m ; i++) {
			if(b[u[i]] > b[v[i]])
				swap(b[u[i]], b[v[i]]);
		}
		for(int i = 1 ; i <= n ; i++)
			if(b[i] != c[i]) {
				return false;
			}
	} while(next_permutation(a + 1, a + 1 + n));
	return true;
}
void init(int p = 0, int val = 0) {
	random_shuffle(a + 1, a + 1 + n);
	for(int i = 1 ; i <= n ; i++)
		if(a[i] == val)
			swap(a[i], a[p]);
}
bool check1() {
	for(int i = 1 ; i <= n ; i++)
		a[i] = i;
	for(int i = 1 ; i <= n ; i++) {
		for(int x = 1 ; x <= 200000 / m ; x++) {
			init(i, n);
			for(int i = 1 ; i <= m ; i++)
				if(a[u[i]] > a[v[i]])
					swap(a[u[i]], a[v[i]]);
			for(int i = 1 ; i <= n ; i++)
				if(a[i] != c[i])
					return false;
		}
	}
	for(int i = 1 ; i <= n ; i++) {
		for(int x = 1 ; x <= 200000 / m ; x++) {
			init(i, 1);
			for(int i = 1 ; i <= m ; i++)
				if(a[u[i]] > a[v[i]])
					swap(a[u[i]], a[v[i]]);
			for(int i = 1 ; i <= n ; i++)
				if(a[i] != c[i])
					return false;
		}
	}
	for(int i = 1 ; i <= 15000000 / m ; i++) {
		for(int i = 1 ; i <= m ; i++)
			if(a[u[i]] > a[v[i]])
				swap(a[u[i]], a[v[i]]);
		for(int i = 1 ; i <= n ; i++)
			if(a[i] != c[i])
				return false;
	}
	return true;
}
signed main() {
	scanf("%lld", &t);
	while(t--) {
		scanf("%lld%lld", &n, &m);
		for(int i = 1 ; i <= m ; i++) {
			scanf("%lld%lld", u + i, v + i);
		}
		for(int i = 1 ; i <= n ; i++)
			c[i] = a[i] = i;
		if(n <= 8) {
			puts(ans[check()].data());
			continue;
		}
		puts(ans[check1()].data());
	}
	exit(0);
}
源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1236kb

input:

10
3 1
2 3
3 3
1 2
1 3
2 3
3 3
1 2
1 3
2 3
3 1
2 3
3 3
1 3
1 2
2 3
4 6
3 4
2 4
1 4
2 3
1 2
1 3
4 6
1...

output:

NO
YES
YES
NO
YES
NO
YES
NO
YES
YES

result:

ok 10 lines

Test #2:

score: 10
Accepted
time: 1ms
memory: 1232kb

input:

10
3 1
2 3
3 3
1 2
1 3
2 3
3 3
1 2
1 3
2 3
3 3
1 2
1 3
2 3
3 2
1 3
2 3
4 6
1 2
1 4
2 3
3 4
1 3
2 4
4...

output:

NO
YES
YES
YES
NO
NO
YES
YES
NO
NO

result:

ok 10 lines

Test #3:

score: 10
Accepted
time: 32ms
memory: 1236kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
8 28
1 8
5 7
1 7
1 5
2 4
4 6
1 6
5 8
1 3
1 4
7 8
2 3
2 8
2 6
4 8
3 6
...

output:

NO
NO
YES
YES
YES
NO
YES
NO
YES
NO

result:

ok 10 lines

Test #4:

score: 10
Accepted
time: 16ms
memory: 1232kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
8 28
2 4
2 6
4 8
1 5
1 6
1 7
2 3
4 5
2 8
5 6
1 3
2 5
3 8
3 4
6 8
1 8
...

output:

NO
NO
NO
NO
NO
YES
NO
NO
YES
NO

result:

ok 10 lines

Test #5:

score: 10
Accepted
time: 42ms
memory: 1236kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
8 28
1 2
3 5
2 7
1 5
4 6
2 3
1 8
2 4
1 6
6 7
1 3
1 7
4 7
2 8
7 8
5 6
...

output:

NO
NO
YES
YES
YES
YES
YES
NO
YES
YES

result:

ok 10 lines

Test #6:

score: 10
Accepted
time: 425ms
memory: 1236kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
10 43
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3...

output:

NO
NO
YES
YES
NO
YES
YES
NO
YES
NO

result:

ok 10 lines

Test #7:

score: 10
Accepted
time: 439ms
memory: 1236kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
10 43
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3...

output:

NO
NO
YES
YES
YES
YES
NO
NO
NO
YES

result:

ok 10 lines

Test #8:

score: 10
Accepted
time: 100ms
memory: 1232kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
10 45
1 2
1 4
1 3
1 5
6 9
6 7
1 6
8 9
7 10
7 9
5 7
1 7
5 8
2 7
2 8
2 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
YES
NO

result:

ok 10 lines

Test #9:

score: 10
Accepted
time: 270ms
memory: 1236kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
10 45
2 9
1 3
1 4
1 5
1 6
1 7
1 8
7 10
1 10
2 6
8 9
2 5
6 9
8 10
6 7
...

output:

NO
NO
YES
YES
NO
NO
NO
NO
YES
NO

result:

ok 10 lines

Test #10:

score: 10
Accepted
time: 355ms
memory: 1236kb

input:

10
4 6
1 2
1 4
2 3
3 4
1 3
2 4
10 45
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 6
2 7
2 8
2 ...

output:

NO
YES
YES
NO
NO
NO
NO
YES
YES
NO

result:

ok 10 lines

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-03-06 02:34:32 | 开源项目