QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#157287#7107. Chaleurucup-team135#AC ✓170ms8684kbC++201.7kb2023-09-02 15:10:142023-09-02 15:10:15

Judging History

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

  • [2023-09-02 15:10:15]
  • 评测
  • 测评结果:AC
  • 用时:170ms
  • 内存:8684kb
  • [2023-09-02 15:10:14]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)
    {
        int n,m;cin>>n>>m;
        vector<int> a[n];for(int i=0;i<m;++i) {int x,y;cin>>x>>y;--x;--y;a[x].push_back(y);a[y].push_back(x);}
        vector<int> v(n);iota(v.begin(),v.end(),0);sort(v.begin(),v.end(),[&](int i,int j) {return a[i].size()>a[j].size();});
        vector<int> cur;bool ok[n]={0};
        for(int i:v)
        {
            int cnt=0;
            for(int j:a[i])
            {
                if(ok[j]) {++cnt;}
            }
            if(cnt==cur.size()) {cur.push_back(i);ok[i]=1;}
        }
        int ways=1;
        for(int i=0;i<n;++i)
        {
            int cnt=0;
            for(int j:a[i])
            {
                if(ok[j]) {++cnt;}
            }
            if(!ok[i] && cnt==cur.size()-1) {++ways;}
        }
        cout<<ways<<' ';
        ways=1;int c=cur.size();bool ok2=0;
        for(int x:cur)
        {
            if(ok[x] && a[x].size()==(c-1))
            {
                ok[x]=0;--c;ok2=1;cur.erase(find(cur.begin(),cur.end(),x));break;
            }
            else if(ok[x] && a[x].size()==c)
            {
                ++ways;
            }
        }
        if(ok2)
        {
            ways=1;
            for(int x:cur)
            {
            if(ok[x] && a[x].size()==(c-1))
            {
                ok[x]=0;--c;ok2=1;cur.erase(find(cur.begin(),cur.end(),x));break;
            }
            else if(ok[x] && a[x].size()==c)
            {
                ++ways;
            }
            }
        }
        cout<<ways<<'\n';
    }
    return 0;
}

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

详细

Test #1:

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

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: 170ms
memory: 8684kb

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