QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#160186 | #7107. Chaleur | ucup-team1447# | AC ✓ | 185ms | 16208kb | C++14 | 2.1kb | 2023-09-02 19:44:01 | 2023-09-02 19:44:02 |
Judging History
answer
#include <bits/stdc++.h>
int T, n, m, rk[100005], maxA, cntA, maxB, cntB;
bool in[100005];
std::vector<int> to[100005];
signed main()
{
std::ios::sync_with_stdio(false);
std::cin >> T;
while (T--)
{
std::cin >> n >> m;
for (int i = 1; i <= n; ++i)
to[i].clear(), rk[i] = i;
for (int i = 1, u, v; i <= m; ++i)
{
std::cin >> u >> v;
to[u].push_back(v);
to[v].push_back(u);
}
std::sort(rk + 1, rk + 1 + n, [&](const int &A, const int &B)
{ return to[A].size() < to[B].size(); });
maxA = maxB = 0;
std::fill(in + 1, in + 1 + n, false);
for (int i = n; i; --i)
{
int cnt = 0;
for (auto j : to[rk[i]])
if (in[j])
++cnt;
if (cnt == n - i)
{
in[rk[i]] = true;
++maxA;
}
}
std::fill(in + 1, in + 1 + n, false);
for (int i = 1; i <= n; ++i)
{
bool flag = true;
for (auto j : to[rk[i]])
if (in[j])
flag = false;
if (flag)
{
in[rk[i]] = true;
++maxB;
}
}
cntA = cntB = 1;
std::fill(in + 1, in + 1 + n, false);
for (int i = n; i; --i)
if (i > n - maxA)
in[rk[i]] = true;
else
{
int cnt = 0;
for (auto j : to[rk[i]])
cnt += in[j];
cntA += cnt == maxA - 1;
}
std::fill(in + 1, in + 1 + n, false);
for (int i = 1; i <= n; ++i)
if (i <= maxB)
in[rk[i]] = true;
else
{
int cnt = 0;
for (auto j : to[rk[i]])
cnt += in[j];
cntB += cnt == 1;
}
std::cout << cntA << ' ' << cntB << std::endl;
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 6084kb
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: 185ms
memory: 16208kb
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