QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#160186#7107. Chaleurucup-team1447#AC ✓185ms16208kbC++142.1kb2023-09-02 19:44:012023-09-02 19:44:02

Judging History

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

  • [2023-09-02 19:44:02]
  • 评测
  • 测评结果:AC
  • 用时:185ms
  • 内存:16208kb
  • [2023-09-02 19:44:01]
  • 提交

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