QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#157287 | #7107. Chaleur | ucup-team135# | AC ✓ | 170ms | 8684kb | C++20 | 1.7kb | 2023-09-02 15:10:14 | 2023-09-02 15:10:15 |
Judging History
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