QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164370 | #7107. Chaleur | linnins | AC ✓ | 274ms | 11308kb | C++14 | 2.8kb | 2023-09-04 22:11:09 | 2023-09-04 22:11:09 |
Judging History
answer
#include<cstdio>
#include<map>
#include<algorithm>
#include<cstring>
#pragma GCC optimize(3)
using namespace std;
int read_int(){
char c;
while(((c = getchar()) < '0' || c > '9') && c != '-');
bool flag = false;
int x = 0;
if(c == '-'){
flag = true;
}
else{
x = c - '0';
}
while((c = getchar()) >= '0' && c <= '9'){
x = x * 10 + c - '0';
}
if(flag)
return -x;
return x;
}
struct Edge{
int v,next;
}Map[200500];
int Head[100500];
struct Node{
long long v;
int i;
}Degree[100500];
void addedge(int num,int from,int go){
Map[num].v = go;
Map[num].next = Head[from];
Head[from] = num;
Degree[from].v += 1;
}
int cmp(Node a,Node b)
{
return a.v>b.v;
}
int solve1(int n,int m,int flag)
{
int i=0;
map<int,int> Mp;
int Ans = 0;
for(i=1;i<=n;i++){
if(Degree[i].v == Ans-1)
break;
Ans+=1;
}
for(int j = i;j <= n;j++){
if(Degree[j].v == Ans)
continue;
Mp[Degree[j].i] = 1;
}
int Final_Ans = 1;
while(Degree[i].v==Ans-1){
int check = 0;
for(int j = Head[Degree[i].i];j!=0;j = Map[j].next){
if(Mp[Map[j].v] == 1){
check = 1;
break;
}
}
if(check == 0){
Final_Ans += 1;
}
i+=1;
}
return Final_Ans;
}
int solve2(int n,int m)
{
int i=0;
map<int,int> Mp;
int Ans = 0;
for(int i=1;i<=n;i++){
Degree[i].v = n-1-Degree[i].v;
}
for(i=n;i>=1;i--){
if(Degree[i].v == Ans-1)
break;
Ans+=1;
}
for(int j = i;j <= n;j++){
if(Degree[j].v == Ans-1)
continue;
Mp[Degree[j].i] = 1;
}
int Final_Ans = 1;
while(Degree[i].v==Ans-1){
int check = 0;
for(int j = Head[Degree[i].i];j!=0;j = Map[j].next){
if(Mp[Map[j].v] == 0){
check += 1;
break;
}
}
if(check == 1){
Final_Ans += 1;
}
i-=1;
}
return Final_Ans;
}
int main()
{
int T;
scanf("%d",&T);
int flag = 0;
while(T--)
{
flag += 1;
int n,m;
scanf("%d%d",&n,&m);
// n = read_int();
// m = read_int();
if(m == 0){
printf("%d %d\n",n,1);
continue;
}
for(int i=0;i<=n+5;i++){
Degree[i].v = 0;
Degree[i].i = i;
Head[i] = 0;
}
int i=0;
for(int j=1;j<=m;j++){
int a,b;
scanf("%d%d",&a,&b);
//a = read_int();
//b = read_int();
addedge(++i,a,b);
addedge(++i,b,a);
}
sort(Degree+1,Degree+n+1,cmp);
int Ans1 = solve1(n,m,flag);
int Ans2 = solve2(n,m);
printf("%d %d\n",Ans1,Ans2);
}
return 0;
}
/*
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
12 11
6 2
6 5
6 7
6 8
6 11
6 9
6 3
6 10
6 4
6 1
6 12
1
15 40
13 14
11 13
8 15
13 3
13 6
10 5
8 11
14 1
15 3
8 14
11 3
11 15
8 12
10 1
8 1
1 6
13 15
11 1
5 15
10 3
10 11
15 1
8 5
15 14
10 15
8 3
13 4
5 1
5 13
10 13
11 14
10 8
14 6
8 13
10 14
13 1
5 14
1 12
11 6
11 5
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5228kb
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: 274ms
memory: 11308kb
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