QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#157535#7107. Chaleurucup-team870#AC ✓174ms17044kbC++171.8kb2023-09-02 15:29:572023-09-02 15:29:57

Judging History

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

  • [2023-09-02 15:29:57]
  • 评测
  • 测评结果:AC
  • 用时:174ms
  • 内存:17044kb
  • [2023-09-02 15:29:57]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 100010;

vector <int> e[N];
int du[N], vis[N], a[N];
// P ksj[N];
bool cmp(int a, int b) {
    return du[a] > du[b];
}
int main() {
    int T; 
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        rep (i, 1, m) {
            int u, v;
            scanf("%d%d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
            du[u]++;
            du[v]++;
        }
        rep (i, 1, n) a[i] = i;
        sort(a+1, a+n+1, cmp);
        int num = 0;
        rep (i, 1, n) {
            int cnt = 0;
            int u = a[i];
            for (int j = 0; j < du[u]; j++) {
                int v = e[u][j];
                cnt += vis[v];
            }
            if (cnt == num) {
                vis[u] = 1;
                num++;
            }
        }

        int ans1 = 0;
        rep (i, 1, n) {
            if (du[i] >= num - 1) ans1++;
        }
        cout << ans1 - num + 1<< ' ';

        int ans2 =0, flag = 0;
        rep (i, 1, n) {
            if (du[i] == num-1 && vis[i]) flag = 1;
        }
        if (flag == 1) {
            rep (i, 1, n) {
                if (du[i] == num-1 && vis[i]) ans2++;
            }
        } else {
            ans2++;
            rep (i, 1, n) {
                if (du[i] == num && vis[i]) ans2++;
            }
        }
        cout << ans2;
        cout <<'\n';
        rep (i, 1, n) {
            du[i] = 0;
            e[i].clear();
            vis[i] = 0;
        }
    }

    return 0;
}

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

详细

Test #1:

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

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: 174ms
memory: 17044kb

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