QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191032#7107. ChaleurGeospiza#AC ✓204ms30356kbC++202.4kb2023-09-29 16:59:392023-09-29 16:59:39

Judging History

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

  • [2023-09-29 16:59:39]
  • 评测
  • 测评结果：AC
  • 用时：204ms
  • 内存：30356kb
查看
  • [2023-09-29 16:59:39]
  • 提交

answer

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
//#define int ll
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(ll i=a;i<=b;++i)
const int N=1e5+5;
ll t,n,m,k,tt;
ll a[N];
vector<ll>vec[N];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
	int T=1;
	cin>>T;
	while(T--)
	{
	    cin>>n>>m;
	    vector<ll>deg(n+1);
	    rep(i,1,n)vec[i].clear();
	    rep(i,1,m)
	    {
            ll u,v;
            cin>>u>>v;
            ++deg[u],++deg[v];
            vec[u].pb(v);
            vec[v].pb(u);
	    }
        vector<pll>v;
        rep(i,1,n)v.pb({deg[i],i});
        sort(all(v));
        vector<ll>add;
        vector<ll>vis(n+1);
        reverse(all(v));
        for(auto x:v)
        {
            if(add.empty())
            {
                add.pb(x.sd);
                vis[x.sd]=1;
            }
            else
            {
                ll sz=0;
                for(auto v:vec[x.sd])if(vis[v])++sz;
                if(sz==add.size())
                {
                    add.pb(x.sd);
                    vis[x.sd]=1;
                }
            }
        }
        ll ans=1;
        for(auto x:v)
        {
            if(vis[x.sd])continue;
            ll sz=0;
            for(auto v:vec[x.sd])if(vis[v])++sz;
            if(sz==(int)add.size()-1)++ans;
        }
        cout<<ans<<" ";
        ans=1;
        reverse(all(v));
        add.clear();
        rep(i,1,n)vis[i]=0;
        for(auto x:v)
        {
            if(add.empty())
            {
                add.pb(x.sd);
                vis[x.sd]=1;
            }
            else
            {
                ll sz=0;
                for(auto v:vec[x.sd])if(vis[v])++sz;
                if(sz==0)
                {
                    add.pb(x.sd);
                    vis[x.sd]=1;
                }
            }
        }
        for(auto x:v)
        {
            if(vis[x.sd])continue;
            ll sz=0;
            for(auto v:vec[x.sd])if(vis[v])++sz;
            if(sz==1)++ans;
        }
        cout<<ans<<"\n";
	}
}
/*
1
5
4 3 1 1 1
5 4 5 3 1


3
5
43111
54531
10
9714785748
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

*/
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 204ms
memory: 30356kb

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
English 繁體中文 简体中文

Server Time: 2024-12-04 23:20:24 | OpenSource Project