QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #191032 | #7107. Chaleur | Geospiza# | AC ✓ | 204ms | 30356kb | C++20 | 2.4kb | 2023-09-29 16:59:39 | 2023-09-29 16:59:39 |
Judging History
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
*/
这程序好像有点Bug，我给组数据试试？
详细
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