QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#163223#7107. ChaleurKKT89AC ✓180ms8312kbC++172.1kb2023-09-03 22:22:572023-09-03 22:22:58

Judging History

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

  • [2023-09-03 22:22:58]
  • 评测
  • 测评结果:AC
  • 用时:180ms
  • 内存:8312kb
  • [2023-09-03 22:22:57]
  • 提交

answer

#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        int n,m;
        cin >> n >> m;
        vector<pair<int,int>> cnt(n);
        for (int i = 0; i < n; ++i) {
            cnt[i].second = i;
        }
        vector<vector<int>> g(n);
        for(int i = 0; i < m; i++) {
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            cnt[a].first++;
            cnt[b].first++;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        sort(cnt.begin(),cnt.end());
        int s = 1;
        for(int i = 0; i < n; i++) {
            int a = n-i;
            s = max(s,min(a,cnt[i].first+1));
        }
        vector<bool> cli(n);
        for (int i = 0; i < s; ++i) {
            cli[cnt[n-1-i].second] = true;
        }
        vector<int> deg(n);
        int res1 = 1;
        for (int i = 0; i < n; ++i) {
            if (!cli[i]) {
                if (g[i].size() == s-1) res1 += 1;
                for (int j : g[i]) {
                    deg[j] += 1;
                }
            }
        }
        int res2 = 0;
        for (int i = 0; i < n; ++i) {
            if (cli[i] and deg[i] == 0) {
                res2 += 1;
            }
        }
        if (res2 == 0) {
            res2 += 1;
            for (int i = 0; i < n; ++i) {
                if (cli[i] and deg[i] == 1) res2 += 1;
            }
        }
        cout << res1 << " " << res2 << "\n";
    }
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

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: 180ms
memory: 8312kb

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