QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#156715 | #7107. Chaleur | ucup-team866# | AC ✓ | 735ms | 68520kb | C++14 | 2.8kb | 2023-09-02 14:06:53 | 2023-09-02 14:52:02 |
Judging History
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