QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#490750 | #8757. 图 | yhddd | RE | 38ms | 20924kb | C++14 | 1.8kb | 2024-07-25 16:20:43 | 2024-07-25 16:20:44 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
return x*f;
}
bool Mbe;
int n,m;
vector<int> f[maxn];
int fd(int id,int x){
if(f[id][x]==x)return x;
return f[id][x]=fd(id,f[id][x]);
}
vector<int> id[maxn];int idx,val[maxn];
vector<int> e[maxn];
int st[maxn],tp;
void dfs(int u,int fa,int ed){
st[++tp]=val[u];
if(st[tp]==ed)return ;
for(int v:e[u])if(v!=fa){
dfs(v,u,ed);
if(st[tp]==ed)return ;
}
tp--;
}
void work(){
n=read();m=read();idx=0;
int k=(m+n-2)/(n-1);
for(int i=1;i<=k;i++){
f[i].resize(n+1);id[i].resize(n+1);
for(int j=1;j<=n;j++)f[i][j]=j,val[id[i][j]=++idx]=j,e[idx].clear();
}
while(m--){
int u=read(),v=read();
int l=1,r=k,res=k+1;
while(l<=r){
int mid=l+r>>1;
if(fd(mid,u)!=fd(mid,v))r=mid-1,res=mid;
else l=mid+1;
}
if(res<=k){
f[res][fd(res,u)]=fd(res,v);
e[id[res][u]].push_back(id[res][v]),e[id[res][v]].push_back(id[res][u]);
}
}
for(int i=1;i<=n;i++)if(fd(k,i)!=i){
int u=i,v=fd(k,i);
printf("%lld %lld\n",u,v);
for(int j=1;j<=k;j++){
tp=0;dfs(id[j][u],0,v);
printf("%lld ",tp);
for(int l=1;l<=tp;l++)printf("%lld ",st[l]);printf("\n");
}
return ;
}
puts("-1");
}
// \
444
bool Med;
int T;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
T=read();
while(T--)work();
}
详细
Test #1:
score: 100
Accepted
time: 38ms
memory: 19896kb
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...
output:
2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2...
result:
ok Answer correct. (10000 test cases)
Test #2:
score: 0
Accepted
time: 23ms
memory: 20580kb
input:
10000 5 20 2 1 2 5 5 3 3 1 4 5 1 4 4 3 4 5 3 5 5 4 2 3 5 2 3 4 3 5 1 4 4 3 4 2 2 1 1 3 5 1 5 20 4 2 1 3 1 2 4 5 2 4 3 1 5 3 5 1 4 5 4 3 2 4 1 4 4 3 5 2 1 2 3 5 1 5 4 1 3 4 4 3 5 20 1 4 1 3 1 5 5 1 4 5 3 4 4 5 2 3 1 2 2 4 4 5 4 5 2 4 2 5 4 2 4 3 4 2 2 5 2 1 3 1 5 20 2 5 2 3 4 5 4 2 3 4 2 1 5 4 2 5 2 ...
output:
1 5 3 1 2 5 3 1 4 5 4 1 4 3 5 4 1 2 4 5 3 1 3 5 1 5 4 1 2 4 5 3 1 3 5 2 1 5 3 1 2 5 2 1 5 2 5 4 2 3 1 5 3 2 1 5 3 2 4 5 3 2 4 5 2 2 5 1 2 2 1 2 2 1 2 4 1 3 5 2 4 1 3 4 2 2 1 2 2 1 4 2 3 5 1 4 2 3 5 1 3 2 3 1 3 2 4 1 4 2 3 5 1 1 5 3 1 4 5 2 1 5 2 1 5 2 1 5 4 1 3 2 5 3 2 ...
result:
ok Answer correct. (10000 test cases)
Test #3:
score: 0
Accepted
time: 21ms
memory: 19392kb
input:
10000 10 20 9 4 8 6 2 10 2 9 7 10 4 6 9 4 2 1 4 7 1 5 7 2 4 1 5 9 7 6 8 2 9 4 5 9 9 8 7 3 2 4 10 20 3 8 8 9 8 7 9 2 3 10 9 3 8 1 9 4 8 9 4 7 7 5 5 10 1 3 3 4 3 7 3 8 3 9 1 4 3 6 2 4 10 20 7 6 8 10 3 8 2 8 4 8 4 8 4 6 4 1 1 7 4 6 5 9 5 2 4 7 10 9 6 7 10 5 2 4 4 1 3 2 4 9 10 20 2 1 9 8 7 6 2 10 9 5 4 ...
output:
2 8 5 2 9 4 6 8 2 2 8 4 2 4 9 8 1 4 4 1 8 9 4 3 1 3 4 2 1 4 4 1 2 4 1 3 4 7 1 2 4 1 4 2 6 4 3 9 5 1 2 2 4 2 3 4 10 2 2 10 4 2 7 4 10 2 2 10 3 2 3 10 1 3 3 1 7 3 3 1 10 3 4 1 8 6 3 3 9 2 3 9 2 3 9 3 3 4 9 1 10 2 1 10 3 1 5 10 2 1 10 7 8 3 7 5 8 2 7 8 2 7 8 4 9 7 4 6 10 1 8 ...
result:
ok Answer correct. (10000 test cases)
Test #4:
score: 0
Accepted
time: 8ms
memory: 19460kb
input:
2000 50 50 6 10 21 26 12 42 29 2 3 30 3 28 7 44 44 37 11 4 23 12 49 14 34 41 35 48 33 6 27 9 33 1 33 31 43 35 32 31 20 42 27 40 39 29 34 38 21 15 31 17 3 33 17 18 15 44 50 22 20 25 28 44 23 32 3 23 25 30 50 20 17 2 21 41 46 35 26 7 34 45 34 19 21 10 44 4 28 22 36 21 4 49 44 39 4 36 2 15 21 38 50 50 ...
output:
2 15 8 2 17 31 33 3 28 44 15 2 2 15 7 10 6 7 36 24 9 37 10 2 7 10 15 24 9 15 34 5 8 1 10 36 14 24 2 15 24 4 19 17 4 10 31 1 47 24 36 28 22 3 13 21 26 42 14 49 19 2 4 19 20 11 4 20 47 35 11 2 20 11 1 45 11 1 24 3 31 12 41 22 9 30 19 45 2 1 45 1 13 3 1 2 13 2 1 13 18 19 7 18 46 42 36 26 ...
result:
ok Answer correct. (2000 test cases)
Test #5:
score: 0
Accepted
time: 26ms
memory: 20552kb
input:
200 50 1000 6 33 31 2 17 37 27 22 36 1 35 12 31 3 8 36 22 15 40 45 13 23 23 24 50 46 41 48 49 35 15 30 14 6 7 24 38 27 43 19 30 16 16 31 49 21 47 44 33 9 27 32 48 23 24 33 25 12 23 50 6 27 20 21 48 11 42 23 8 36 3 34 8 14 17 30 27 1 14 40 37 5 23 24 6 24 5 35 38 43 31 48 25 33 4 13 6 37 22 24 31 32 ...
output:
2 9 10 2 31 16 30 15 22 27 6 33 9 12 2 8 36 47 1 27 6 24 23 11 35 9 6 2 44 15 46 36 9 12 2 37 23 3 36 13 7 24 22 25 34 9 4 2 37 49 9 7 2 44 42 37 14 35 9 6 2 44 41 15 32 9 8 2 42 21 10 39 28 14 9 6 2 1 42 10 41 9 7 2 44 5 11 41 22 9 13 2 5 20 1 33 24 35 21 28 32 10 22 9 10 2 16 29 40 8 20...
result:
ok Answer correct. (200 test cases)
Test #6:
score: 0
Accepted
time: 30ms
memory: 20924kb
input:
20 100 10000 77 84 14 62 84 5 4 67 99 44 54 18 39 53 58 88 32 3 61 19 76 14 28 72 92 34 20 1 14 66 98 25 53 99 55 40 13 70 42 62 32 41 93 14 74 66 92 62 42 12 94 35 26 65 82 85 100 34 79 47 87 59 4 92 46 4 77 63 17 62 32 23 46 76 61 26 89 41 10 18 17 64 55 61 89 42 8 71 75 89 2 81 9 63 42 32 23 34 7...
output:
5 6 14 5 84 77 63 76 14 62 42 89 20 99 48 91 6 7 5 64 41 87 60 67 6 12 5 66 96 91 72 46 98 31 76 94 69 6 12 5 73 39 68 71 72 98 36 63 65 74 6 11 5 47 17 76 20 42 26 78 33 95 6 12 5 18 96 29 27 76 14 57 62 71 91 6 12 5 31 65 86 15 10 13 43 99 88 80 6 9 5 41 77 43 46 1 49 40 6 14 5 29 36 98 30...
result:
ok Answer correct. (20 test cases)
Test #7:
score: 0
Accepted
time: 17ms
memory: 20004kb
input:
100 1000 1999 527 98 626 570 505 814 510 660 334 873 893 329 51 818 256 113 165 543 515 780 905 200 560 363 385 813 82 324 661 719 3 624 175 120 22 480 662 730 701 676 124 107 820 707 288 412 596 842 285 574 209 109 897 789 37 371 399 502 715 361 877 504 68 73 919 671 685 732 866 390 975 122 994 263...
output:
2 50 7 2 316 806 355 20 721 50 52 2 361 111 758 966 773 539 479 541 257 684 483 185 866 910 515 571 724 450 216 614 552 757 26 902 429 57 716 598 876 90 315 972 546 312 703 756 968 278 313 999 820 569 89 357 407 67 453 937 517 532 50 2 2 50 1 945 10 1 411 850 668 346 821 513 813 746 945 27 1 258...
result:
ok Answer correct. (100 test cases)
Test #8:
score: 0
Accepted
time: 7ms
memory: 19976kb
input:
1000 100 100 8 93 14 86 43 53 73 87 9 5 30 87 23 88 9 18 89 75 49 53 39 91 58 22 86 27 75 1 57 90 20 40 71 55 58 77 63 46 97 95 6 71 19 92 54 24 50 96 30 50 11 79 70 20 79 24 88 33 8 86 18 60 51 58 66 39 93 31 1 47 41 65 45 12 3 93 62 33 38 49 29 91 3 29 15 51 37 56 54 6 85 95 2 81 36 28 10 98 57 26...
output:
78 56 24 78 23 88 33 62 9 70 20 40 43 53 76 27 86 8 93 3 29 91 87 30 50 96 56 2 78 56 18 45 11 18 85 59 69 1 23 75 47 13 93 45 2 18 45 9 92 9 9 69 24 30 15 34 85 57 92 2 9 92 7 60 23 7 99 61 63 43 84 78 26 13 98 55 72 15 42 76 21 75 23 88 86 67 87 60 2 7 60 13 57 16 13 70 19 71 4 74 86 93 46...
result:
ok Answer correct. (1000 test cases)
Test #9:
score: 0
Accepted
time: 18ms
memory: 19492kb
input:
500 200 399 181 137 41 68 61 54 32 10 41 136 85 112 127 111 51 107 143 189 21 69 149 109 107 120 21 158 175 53 31 48 80 170 46 108 163 85 110 142 2 30 117 128 109 114 142 178 76 43 118 63 36 149 45 74 165 123 43 72 87 185 70 173 132 79 130 163 187 10 189 114 70 22 12 184 200 175 65 169 23 27 1 14 19...
output:
11 27 4 11 16 23 27 20 11 144 37 192 106 17 20 160 157 14 114 161 44 2 26 64 167 164 10 27 2 11 27 2 71 25 2 97 105 127 43 95 139 100 3 185 98 121 173 191 167 120 4 31 124 57 33 64 128 10 71 26 2 13 197 67 100 177 159 138 24 27 25 162 83 88 176 50 89 78 161 127 142 125 147 133 193 71 2 2 71 8 ...
result:
ok Answer correct. (500 test cases)
Test #10:
score: 0
Accepted
time: 21ms
memory: 19452kb
input:
2197 10 91 7 3 7 9 9 2 1 10 7 1 6 8 4 8 2 10 7 6 5 3 4 10 9 3 1 4 2 9 5 4 5 6 3 7 6 1 1 9 2 6 3 4 6 9 8 7 6 7 7 4 8 7 9 3 10 7 10 6 2 5 2 7 8 10 10 1 7 4 10 4 9 2 7 6 3 10 6 4 1 8 8 9 6 7 10 9 3 2 2 5 10 5 4 7 5 3 9 4 1 5 1 4 8 4 4 10 7 3 6 7 4 2 3 4 9 2 1 10 6 1 8 3 2 9 9 10 9 5 3 4 5 8 9 3 7 1 6 1...
output:
2 4 6 2 9 7 6 8 4 3 2 10 4 4 2 6 7 4 3 2 7 4 3 2 9 4 5 2 3 5 1 4 2 2 4 2 2 4 5 2 10 5 6 4 2 2 4 2 2 4 4 7 3 4 2 7 3 4 2 7 3 4 2 7 2 4 7 4 4 8 2 7 3 4 9 7 4 4 5 8 7 4 4 8 1 7 3 4 2 7 2 4 7 2 4 7 2 5 3 2 8 5 6 2 6 7 1 9 5 3 2 6 5 3 2 6 5 3 2 1 5 5 2 1 7 8 5 5 2 4 9 3 5 5 2...
result:
ok Answer correct. (2197 test cases)
Test #11:
score: 0
Accepted
time: 31ms
memory: 19896kb
input:
1980 5 101 3 5 4 2 5 1 1 4 2 5 1 3 2 5 3 2 4 2 3 1 1 2 5 3 3 4 3 1 1 3 5 3 1 4 2 4 2 3 4 2 4 5 4 5 1 2 3 1 3 4 1 2 3 5 4 1 2 4 3 5 4 3 4 1 2 1 2 1 5 4 5 3 3 5 2 5 4 1 5 3 2 3 3 4 3 4 5 2 3 2 4 3 2 3 4 3 1 5 2 1 1 3 1 4 1 4 2 5 2 1 1 3 3 5 5 3 1 5 3 4 4 2 3 5 4 2 2 4 4 1 3 5 3 5 5 4 1 4 5 3 5 1 5 3 1...
output:
1 3 3 1 5 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 4 1 4 5 3 3 1 4 3 4 1 2 5 3 3 1 2 3 3 1 5 3 3 1 2 3 2 1 3 3 1 4 3 2 1 3 3 1 4 3 4 1 4 5 3 3 1 5 3 3 1 4 3 3 1 5 3 2 1 3 4 1 2 5 3 2 1 3 2 1 3 2 1 3 2 1 3 2 4 4 2 1 3 4 3 2 3 4 3 2 3 4 4 2 5 1 4 2 2 4 2 2 4 4 2 3 1 4 3 2 5 4 ...
result:
ok Answer correct. (1980 test cases)
Test #12:
score: -100
Runtime Error
input:
1 100000 200000 34863 14128 21925 31963 32836 60679 64214 73508 66150 45252 9601 33518 33904 58681 94179 37263 91962 58845 44150 57595 75389 55087 95549 80645 35339 82663 93639 89411 91288 79966 6158 91046 34153 16675 38098 20451 49822 20670 34821 40807 67167 98424 75186 55129 47388 80048 47576 3327...