QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156715#7107. Chaleurucup-team866#AC ✓735ms68520kbC++142.8kb2023-09-02 14:06:532023-09-02 14:52:02

Judging History

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

  • [2023-09-02 14:52:02]
  • 评测
  • 测评结果:AC
  • 用时:735ms
  • 内存:68520kb
  • [2023-09-02 14:06:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5, M = 2e7 + 7;
int T, n, m, u, v, edgenum, Head[N], Next[M], vet[M], nodes, cnt, TIME, id[N], top, stk[N], instk[N], low[N], dfn[N], t[N], s[2][N], c[2], bid[N];
basic_string <int> adj[100005];
void add(int u, int v) {
	Next[++edgenum] = Head[u];
	Head[u] = edgenum;
	vet[edgenum] = v;
}
void build(int p, int l, int r) {
	if (l == r) return void (id[p] = l);
	int mid = l + r >> 1;
	id[p] = ++ nodes;
	build(p<<1, l, mid), add(id[p], id[p<<1]);
	build(p<<1|1, mid+1, r), add(id[p], id[p<<1|1]);
}
void update(int p, int l, int r, int x, int y, int z) {
	if (l == x && r == y) return add(z, id[p]);
	int mid = l + r >> 1;
	if (y <= mid) update(p<<1, l, mid, x, y, z);
	else if (x > mid) update(p<<1|1, mid+1, r, x, y, z);
	else update(p<<1, l, mid, x, mid, z), update(p<<1|1, mid+1, r, mid+1, y, z);
}
void Tarjan(int u, int fa) {
	low[u] = dfn[u] = ++ TIME, stk[++top] = u, instk[u] = 1;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (! dfn[v]) Tarjan(v, u), low[u] = min(low[u], low[v]);
		else if (instk[v]) low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		cnt ++;
		do bid[stk[top]] = cnt, instk[stk[top]] = 0;
		while (stk[top--] ^ u);
	}
}
int main() {
	cin >> T;
	while (T --) {
		scanf ("%d%d", &n, &m);
		if (! m) { printf ("%d %d\n", n, 1); continue; }
		if (m == n * (n - 1) >> 1) { for (int i=1; i<=m; i++) scanf ("%*d%*d"); printf ("%d %d\n", 1, n); continue; }
		for (int i=1; i<=n; i++)
			adj[i]. clear(), adj[i] += i; edgenum = 0;
		for (int i=1; i<=m; i++) {
			scanf ("%d%d", &u, &v), adj[u] += v, adj[v] += u;
			add(u, n + v), add(v, n + u);
		} nodes = n << 1;
		build(1, 1, n);
		for (int i=1; i<=n; i++) {
			int l = 0;
			sort (adj[i]. begin(), adj[i]. end());
			for (int j : adj[i]) {
				if (l + 1 < j) update(1, 1, n, l + 1, j - 1, n + i); //, cerr << n + i << ' ' << l + 1 << ',' << j - 1 << endl;
				l = j;
			}
			if (l < n) update(1, 1, n, l + 1, n, n + i); //, cerr << n + i << ' ' << l + 1 << ',' << n << endl;
		} cnt = TIME = 0;
		for (int i=1; i<=nodes; i++)
			dfn[i] = 0;
		for (int i=1; i<=nodes; i++)
			if (! dfn[i]) Tarjan(i, 0);
		c[0] = c[1] = 0;
		for (int i=1; i<=n; i++)
			t[i] = bid[i] > bid[n+i], s[t[i]][++c[t[i]]] = i; //, cerr << t[i]; cerr << endl;
		int mx = - 1, mc;
		for (int i=1; i<=c[0]; i++) {
			int now = 0;
			for (int j : adj[s[0][i]]) now += t[j];
			if (now > mx) mx = now, mc = 0;
			if (now == mx) mc ++;
		}
		printf ("%d ", mx == c[1] ? mc : mx == c[1] - 1 ? mc + 1 : 1);
		mx = - 1;
		for (int i=1; i<=c[1]; i++) {
			int now = c[0];
			for (int j : adj[s[1][i]]) now -= ! t[j];
			if (now > mx) mx = now, mc = 0;
			if (now == mx) mc ++;
		}
		printf ("%d\n", mx == c[0] ? mc : mx == c[0] - 1 ? mc + 1 : 1);
		for (int i=1; i<=nodes; i++)
			Head[i] = 0;
	}
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 24792kb

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: 735ms
memory: 68520kb

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