QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#204548 | #7107. Chaleur | thangthang | AC ✓ | 127ms | 16396kb | C++14 | 1.3kb | 2023-10-07 13:07:01 | 2023-10-07 13:07:01 |
Judging History
answer
#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int n, m, deg[N];
vector <int> c[N];
int sr[N];
void solve(){
cin >> n >> m;
for (int i = 1; i <= n; ++ i) deg[i] = 0, c[i].clear();
for (int i = 1; i <= m; ++ i){
int u, v; cin >> u >> v;
c[u].push_back(v);
c[v].push_back(u);
deg[u] ++;
deg[v] ++;
}
for (int i = 1; i <= n; ++ i) {
sr[i] = i;
}
sort(sr + 1, sr + n + 1, [&](int u, int v) {
return deg[u] > deg[v];
});
int cnt = 0;
int ans = 0;
int gg = 1;
for (int i = n; i >= 1; -- i){
if (deg[sr[i]] >= i - 1){
for (int j = i + 1; j <= n; ++ j) if (deg[sr[j]] == i - 1) ++ cnt;
for (int j = 1; j <= i; ++ j) if (deg[sr[j]] == i - 1) ++ ans;
for (int j = 1; j <= i; ++ j) if (deg[sr[j]] == i) ++ gg;
break;
}
}
if (ans == 0) ans = gg;
cout << cnt + 1 << ' ' << ans << '\n';
}
int main(){
//freopen("code.inp", "r", stdin);
//freopen("code.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while (t --) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5816kb
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: 127ms
memory: 16396kb
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