QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#429702 | #5239. Mędrcy [A] | qwqUwU_ | 0 | 15ms | 4100kb | C++20 | 2.2kb | 2024-06-02 19:26:29 | 2024-06-02 19:26:30 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcount(s)
#define lb(s) (s&-s)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
inline ll read(){
ll x=0,f=1,c=getchar();
while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
while(c>='0' && c<='9')x=x*10 + c-'0',c=getchar();
return x*f;
}
const int N=1e3+3;
const int mod=998244353;
inline void Ad(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int n,m,k;
bitset<N>bs,ans;int res;
pii p[3*N];
int d[N];
bool vis[N];
int inq[N];
vector<int>G[N],vec;
inline void dfs2(int u){
vis[u]=1;vec.pb(u);
for(auto v:G[u])if(!vis[v])dfs2(v);
}
inline void dfs(int k){
rep(i,1,n)d[i]=0;
rep(i,1,m)if(!bs[p[i].fi] && !bs[p[i].se])++d[p[i].fi],++d[p[i].se];
int bst=1;
rep(i,2,n)if(d[bst]<d[i])bst=i;
if(d[bst]<=2){
auto tmp=bst;
rep(i,1,n)vis[i]=0,G[i].clear();
rep(i,1,m)if(!bs[p[i].fi] && !bs[p[i].se]){
int u=p[i].fi,v=p[i].se;
G[u].pb(v),G[v].pb(u);
}
rep(i,1,n)if(!vis[i] && !bs[i] && d[i]==1){
vec.clear(); dfs2(i);
int m=vec.size();k += m>>1;
for(int i=m&1;i<m;i+=1+(m&1))bs.set(vec[i]);
}
rep(i,1,n)if(!vis[i] && !bs[i] && d[i]==2){
vec.clear(); dfs2(i);
int m=vec.size();k += (m+1)>>1;
rep(i,0,m-1)bs.set(vec[i]);
}
if(k<res) res=k,ans.reset();
if(res==k)ans|=bs;
return ;
}
bs.set(bst);dfs(k+1);bs.reset(bst);
rep(i,1,m)if(!bs[p[i].fi] && !bs[p[i].se] && (p[i].fi==bst || p[i].se==bst)){
if(p[i].se==bst)swap(p[i].fi,p[i].se);
++k;bs.set(p[i].se);
}
dfs(k);
rep(i,1,m)if(!bs[p[i].fi] && !bs[p[i].se] && p[i].fi==bst) bs.reset(p[i].se);
}
inline void solve(){
n=read(),m=read(),k=read();
bs.reset(),ans.reset();res=n;
rep(i,1,m){
p[i].fi=read(),p[i].se=read();
}
dfs(0);
if(res>k){ puts("-1"); return ; }
printf("%d %d\n",res,ans.count());
for(int i=ans._Find_first();i<=n;i=ans._Find_next(i))printf("%d ",i);
puts("");
}
int main(){
//freopen("data.in","r",stdin);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int T=read();while(T--)solve();
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3768kb
input:
136 9 37 11 2 7 2 5 2 5 6 8 2 4 2 9 4 5 6 8 6 7 3 9 3 6 3 8 1 9 2 9 4 6 2 4 1 4 7 9 7 9 4 7 3 6 4 5 2 7 1 5 6 9 4 9 4 5 2 7 3 9 1 9 2 7 5 7 1 2 2 3 1 8 3 8 1 3 7 1 13 4 6 3 36 2 2 3 2 3 1 2 2 3 1 3 1 3 1 3 1 2 1 2 1 2 1 2 1 2 1 3 1 2 1 3 1 3 1 2 1 3 1 2 1 3 1 2 2 3 1 2 1 3 1 3 2 3 1 3 2 3 2 3 1 2 1 ...
output:
1 8 1 3 4 5 6 7 8 9 1 2 4 6 1 2 2 3 1 2 1 2 0 6 1 2 3 5 8 9 1 6 2 3 4 5 6 7 1 3 1 3 4 0 7 2 3 5 6 7 8 9 0 6 3 4 5 6 7 9 2 9 2 3 4 5 6 7 8 9 10 1 9 1 2 3 4 5 6 8 9 10 1 5 2 3 4 5 6 1 4 2 3 4 5 1 8 1 2 6 8 9 10 11 12 1 2 2 3 1 3 1 2 3 1 5 1 3 4 5 6 3 6 1 2 3 4 5 6 1 4 2 3 4 5 3 9 1 ...
result:
wrong answer 1st lines differ - expected: '6 6', found: '1 8'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 3744kb
input:
139 11 16 6 3 4 1 3 5 7 3 6 3 9 7 10 3 8 1 2 4 8 1 11 4 8 4 9 3 6 4 9 5 9 1 6 8 23 11 2 4 4 8 3 6 4 5 1 3 5 7 3 8 2 5 1 6 1 5 5 8 6 7 1 3 3 5 6 7 7 8 6 8 5 8 4 6 4 8 2 3 1 5 2 8 11 31 1 5 11 3 11 5 7 1 9 3 5 3 5 1 2 1 5 5 7 9 10 2 6 2 7 2 9 5 9 1 11 5 8 4 8 5 6 4 10 3 10 2 9 7 11 5 9 2 6 8 9 9 10 8 ...
output:
2 11 1 2 3 4 5 6 7 8 9 10 11 0 6 1 2 3 4 7 8 1 8 1 3 4 6 7 8 9 11 1 6 1 2 3 4 5 7 1 11 1 3 4 5 6 7 8 9 10 11 12 1 7 2 3 5 6 7 8 9 1 5 1 2 4 5 6 -1 1 1 10 0 2 1 3 2 4 5 6 9 10 1 7 1 2 4 5 6 7 8 1 4 1 2 4 5 1 5 2 3 4 5 6 1 3 1 3 4 2 11 1 2 3 4 5 6 7 8 9 10 11 1 2 1 3 1 4 2 3 4 5 1 4 1...
result:
wrong answer 1st lines differ - expected: '5 8', found: '2 11'
Subtask #3:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1ms
memory: 4084kb
input:
66 20 51 30 2 4 5 8 19 20 10 11 7 12 1 20 5 13 12 14 13 15 11 14 4 5 9 16 14 15 5 9 6 14 5 6 3 16 9 18 6 8 14 19 7 8 12 15 8 17 11 14 4 9 11 20 2 13 3 18 5 20 11 13 13 18 3 17 15 20 8 13 4 10 1 6 3 5 7 8 12 14 2 20 4 15 3 20 8 9 3 20 2 16 3 10 2 7 5 19 3 8 8 20 7 10 15 58 30 7 15 8 13 3 13 3 8 4 8 1...
output:
1 18 1 2 3 4 5 6 7 9 10 11 12 13 15 16 17 18 19 20 1 14 1 2 3 5 6 7 8 9 10 11 12 13 14 15 2 10 2 5 6 7 8 9 10 11 12 13 1 10 1 2 3 4 5 6 7 8 9 10 0 14 1 2 3 4 5 6 7 10 11 12 13 14 15 16 1 13 2 3 4 5 6 7 8 9 10 11 12 13 14 2 15 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 1 13 1 2 3 4 6 7 8 9 10 11 12 ...
result:
wrong answer 1st lines differ - expected: '12 17', found: '1 18'
Subtask #4:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 1ms
memory: 3768kb
input:
67 11 28 30 1 7 1 5 4 11 1 2 2 10 9 11 8 9 7 9 4 8 4 9 5 8 5 7 5 8 2 11 8 10 1 3 2 11 5 8 2 4 7 10 8 11 6 11 2 4 2 11 1 6 10 11 8 11 3 8 10 44 30 5 8 1 4 1 4 3 9 1 4 6 7 3 8 6 7 4 8 4 6 1 2 4 7 1 8 1 5 9 10 2 10 7 8 2 8 1 9 1 5 5 10 1 7 4 6 7 10 2 5 4 8 6 8 8 9 7 10 6 10 4 10 3 5 2 9 6 10 4 8 5 10 5...
output:
0 9 1 3 4 5 6 7 9 10 11 1 8 2 3 4 5 6 7 8 9 1 9 1 2 3 4 5 7 8 10 11 3 15 2 3 4 5 6 7 8 9 10 11 12 14 15 17 18 1 10 1 2 3 4 5 8 10 11 12 13 0 8 1 3 4 6 8 10 11 13 0 9 1 2 5 6 7 8 9 10 12 1 9 1 2 3 4 5 6 7 8 10 1 8 1 2 5 6 8 9 10 11 2 13 1 2 3 4 5 6 7 8 9 10 12 13 14 0 8 1 2 4 5 6 8 9 10 1 ...
result:
wrong answer 1st lines differ - expected: '6 8', found: '0 9'
Subtask #5:
score: 0
Wrong Answer
Test #47:
score: 0
Wrong Answer
time: 1ms
memory: 4008kb
input:
64 16 32 30 8 13 8 11 5 12 3 10 3 8 6 15 12 13 5 7 1 2 8 14 2 4 8 16 14 15 3 13 6 9 1 11 4 8 15 16 9 12 10 16 4 8 4 5 3 6 3 15 6 14 5 11 3 11 1 15 4 15 6 13 8 14 7 13 15 42 30 1 4 5 13 12 13 9 12 4 9 10 11 9 11 5 6 2 6 3 11 5 14 8 11 4 7 1 15 6 14 2 14 4 11 1 5 6 8 1 7 1 5 9 14 7 15 7 8 5 7 3 9 12 1...
output:
0 13 1 2 3 4 6 7 9 10 11 12 13 14 16 1 13 1 2 3 4 6 7 8 9 10 12 13 14 15 1 9 1 2 4 5 6 7 8 9 10 0 9 2 3 4 5 6 7 8 9 11 1 15 1 2 4 6 7 8 9 10 11 12 13 14 15 16 17 0 10 1 3 5 7 8 9 10 12 14 16 2 12 3 4 5 6 7 9 10 11 13 14 16 17 1 15 1 2 3 5 6 8 10 11 12 13 14 15 16 17 18 2 13 2 3 4 6 7 8 10 11...
result:
wrong answer 1st lines differ - expected: '9 10', found: '0 13'
Subtask #6:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 0ms
memory: 3736kb
input:
32 23 77 30 4 18 1 20 11 20 6 22 7 18 2 17 10 14 3 6 15 22 3 13 14 17 4 16 14 23 1 10 9 14 6 20 4 9 11 16 20 22 5 13 3 23 8 20 2 16 12 16 5 20 1 19 3 8 9 17 15 21 18 23 1 6 3 16 2 6 16 22 16 22 6 15 14 21 4 22 12 19 10 21 2 18 1 10 15 22 7 20 6 19 13 22 5 16 7 22 21 23 14 15 5 16 11 20 10 16 18 19 5...
output:
0 18 1 2 3 4 5 7 8 10 11 12 13 14 15 17 19 20 22 23 3 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 33 1 2 3 4 5 6 7 8 10 12 13 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 1 27 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 24 25 26 27 28 1 29 2 4 5 6...
result:
wrong answer 1st lines differ - expected: '13 14', found: '0 18'
Subtask #7:
score: 0
Wrong Answer
Test #78:
score: 0
Wrong Answer
time: 1ms
memory: 4028kb
input:
36 20 64 30 5 6 7 14 14 18 13 17 15 16 15 18 2 13 6 20 3 8 10 16 10 20 12 14 15 17 3 4 3 11 6 12 8 11 11 14 8 16 12 20 3 4 18 20 9 12 16 20 11 17 4 7 2 9 12 18 18 20 3 15 12 17 1 7 3 11 1 16 12 20 1 6 8 20 10 19 10 15 14 18 14 18 3 16 3 7 12 19 2 17 4 11 12 20 1 12 5 8 10 17 18 19 12 19 3 17 11 19 3...
output:
1 18 1 2 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 1 23 1 3 4 5 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 28 29 3 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 27 3 4 5 7 12 13 14 15 16 17 19 20 21 22 23 25 28 29 30 31 32 33 34 35 36 37 38 1 24 1 3 4 6 9 10 11 12 14...
result:
wrong answer 1st lines differ - expected: '12 15', found: '1 18'
Subtask #8:
score: 0
Wrong Answer
Test #97:
score: 0
Wrong Answer
time: 15ms
memory: 4100kb
input:
1 1000 3000 30 82 508 127 347 370 658 350 586 486 863 28 99 293 422 427 710 731 936 555 856 91 374 133 676 351 806 780 992 132 686 73 813 212 971 161 919 402 666 59 106 682 766 288 570 199 882 332 428 633 693 306 694 319 882 356 582 546 916 305 665 336 534 608 901 222 228 422 860 406 869 457 524 114...
output:
2 879 1 2 3 4 5 6 7 8 9 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 32 33 34 35 36 37 38 39 40 41 42 45 46 47 49 50 52 53 54 55 56 57 58 59 60 61 62 64 66 67 68 69 71 72 73 74 75 76 77 78 79 82 83 84 86 87 88 90 91 92 93 96 97 98 99 101 102 103 104 106 107 108 109 110 112 113 114 115 116 117 118...
result:
wrong answer 1st lines differ - expected: '-1', found: '2 879'
Subtask #9:
score: 0
Wrong Answer
Test #109:
score: 0
Wrong Answer
time: 11ms
memory: 3780kb
input:
1 1000 3000 30 126 407 55 812 361 478 617 796 500 641 338 450 587 739 1 159 753 795 521 995 313 981 35 595 364 914 334 672 615 802 466 789 262 852 258 867 475 686 543 902 334 795 470 899 146 823 713 850 305 574 201 332 119 298 387 747 187 999 95 981 349 731 749 883 829 895 380 818 568 856 738 981 69...
output:
4 870 1 2 4 5 6 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30 32 33 35 36 37 41 42 43 44 46 49 50 51 52 53 54 55 56 57 58 60 62 63 64 66 67 68 69 70 71 72 73 74 75 76 77 78 79 81 82 83 84 85 87 88 89 90 91 92 94 95 96 97 98 99 100 101 103 104 105 107 108 109 111 112 113 116 117 118 11...
result:
wrong answer 1st lines differ - expected: '-1', found: '4 870'
Subtask #10:
score: 0
Wrong Answer
Test #121:
score: 0
Wrong Answer
time: 2ms
memory: 3768kb
input:
1 1000 3000 30 530 695 780 873 245 704 66 567 435 786 5 536 743 895 374 505 283 773 10 50 250 840 100 416 321 704 390 1000 786 921 374 549 490 626 362 759 661 929 589 704 390 446 123 725 371 447 380 930 10 106 661 876 615 695 410 695 421 695 390 561 10 209 338 780 18 345 41 123 121 773 345 384 558 9...
output:
6 940 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 66 67 68 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 88 89 90 92 93 94 95 96 97 98 99 100 101 102 103 104 105 ...
result:
wrong answer 1st lines differ - expected: '29 29', found: '6 940'