QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204003#7107. Chaleurucup-team484AC ✓250ms37520kbC++171.5kb2023-10-06 23:37:192023-10-06 23:37:20

Judging History

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

  • [2023-10-06 23:37:20]
  • 评测
  • 测评结果:AC
  • 用时:250ms
  • 内存:37520kb
  • [2023-10-06 23:37:19]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
vector<int> adj[N];

void solve() {
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
		adj[i].clear();
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<int> idx(n);
	iota(all(idx), 0);
	sort(all(idx), [&](int i, int j) {
		return sz(adj[i]) < sz(adj[j]);
	});
	for (int i = 0; i < n; i++) {
		sort(adj[i].begin(), adj[i].end(), [&](int u, int v) {
			return idx[u] > idx[v];
		});
	}

	auto is_conn = [&](int u, int v) {
		auto it = lower_bound(all(adj[u]), v, [&](int i, int j) {
			return idx[i] > idx[j];
		});
		if (it != adj[u].end() && *it == v)
			return 1;
		return 0;
	};

	vector<int> cl, vis(n);
	for (int i = n - 1; i >= 0; i--) {
		int o = 1;
		for (int j: cl) {
			o &= is_conn(idx[i], j);
			if (o == 0)
				break;
		}
		if (o == 0) {
			int x = 1, y = 1;
			for (int j = i; j >= 0; j--)
				x += sz(adj[idx[j]]) == sz(cl) - 1;
			if (sz(adj[idx[i+1]]) == sz(cl) - 1)
				i++, cl.pop_back();
			for (int j: cl)
				y += sz(adj[j]) <= sz(cl);
			cout << x << " " << y << "\n";
			return;
		}
		vis[idx[i]] = 1;
		cl.push_back(idx[i]);
	}
	cout << 1 << " " << n << "\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t; cin >> t; while (t--) solve();
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 27080kb

input:

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

output:

2 1
1 4
1 2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 250ms
memory: 37520kb

input:

2231
1 0
5 7
4 1
3 4
3 1
3 5
4 2
3 2
4 5
5 4
2 1
2 5
2 4
2 3
5 10
3 2
2 5
1 4
4 2
4 5
1 2
1 3
3 5
3 4
1 5
5 10
1 3
2 4
1 4
5 2
2 3
1 5
5 4
1 2
3 4
5 3
5 9
2 5
3 5
2 3
2 1
4 3
3 1
4 1
4 5
2 4
5 4
4 2
4 1
4 5
4 3
5 9
4 1
4 5
3 4
2 4
2 1
3 1
2 5
3 5
3 2
5 4
2 5
2 3
2 1
2 4
5 9
5 2
1 3
4 3
1 2
5 4
4 2
5...

output:

1 1
3 1
4 1
1 5
1 5
2 1
4 1
2 1
4 1
2 1
2 1
3 1
4 1
4 1
1 5
2 1
4 1
1 5
1 5
1 5
3 1
4 1
4 1
4 1
3 1
3 1
4 1
4 1
2 1
4 1
4 1
1 5
1 5
2 1
4 1
4 1
4 1
3 1
2 1
4 1
2 1
4 1
4 1
4 1
3 1
1 5
4 1
4 1
1 5
2 1
4 1
2 1
2 1
1 5
4 1
1 5
3 1
4 1
1 5
2 1
1 5
3 1
3 1
1 5
3 1
3 1
2 1
1 5
4 1
3 1
1 5
2 1
3 1
2 1
2 1
...

result:

ok 2231 lines

Extra Test:

score: 0
Extra Test Passed