QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155858#5522. F*** 3-Colorable Graphsdanielkou5855TL 17ms7444kbC++20661b2023-09-02 11:23:162023-09-02 11:23:16

Judging History

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

  • [2023-09-02 11:23:16]
  • 评测
  • 测评结果:TL
  • 用时:17ms
  • 内存:7444kb
  • [2023-09-02 11:23:16]
  • 提交

answer

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0) -> sync_with_stdio(0);

	int N, M; cin >> N >> M;

	vector<vector<int>> adj(2 * N);

	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; a--; b--;

		adj[a].push_back(b); adj[b].push_back(a);
	}

	set<pair<int, int>> visited;

	for (int i = 0; i < 2 * N; i++) {
		for (auto j : adj[i]) {
			for (auto k : adj[i]) {
				if (j == k) {
					continue;
				}
				
				if (visited.count({j, k})) {
					cout << 2 << "\n";
					return 0;
				}

				visited.insert({j, k});
			}
		}
	}

	cout << 3 << "\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

input:

2 4
1 3
1 4
2 3
2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3632kb

input:

3 5
1 4
2 4
2 5
3 5
3 6

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 17ms
memory: 7444kb

input:

10000 20000
4570 11730
8803 16440
4257 15381
4455 17636
5256 13543
2172 18421
7735 17847
8537 16010
6175 12263
1079 13410
335 15901
3272 16233
7435 11454
4469 13374
1564 13416
1264 13446
7484 14510
8193 12267
628 15585
1388 11398
5444 19958
2059 18140
8947 13188
6214 17707
7940 12253
6726 11508
1839...

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: -100
Time Limit Exceeded

input:

9999 199986
8408 17344
1353 16706
3364 17274
9410 10006
9387 19375
9169 18239
3930 12759
4728 11328
5192 17935
7616 19485
3138 12714
8595 18490
6020 15039
9319 17097
7842 16814
7644 18723
2190 10117
3971 13350
232 15408
6984 12842
6988 17196
9744 18905
6759 13371
4115 18937
1842 13513
6245 18736
207...

output:


result: