QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#68137#4883. Bayan TestingA_zjzjWA 48ms3804kbC++14635b2022-12-14 19:01:532022-12-14 19:01:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-14 19:01:55]
  • 评测
  • 测评结果：WA
  • 用时：48ms
  • 内存：3804kb
查看
  • [2022-12-14 19:01:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=2e5+10;
int T,n,m,cnt,fa[N];struct zj{int l,r;}a[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
void get(){
	cnt=0;scanf("%d%d",&n,&m);for(int i=1;i<=m*2;i++)scanf("%d%d",&a[i].l,&a[i].r);
	iota(fa,fa+1+n,0);sort(a+1,a+1+m*2,[](zj x,zj y){return x.l^y.l?x.l<y.l:x.r>y.r;});
	for(int i=1;i<=m*2&&cnt<m;i++)if(a[i].l^a[i].r)cnt++,merge(a[i].l,a[i].r);
	if(cnt<m)puts("-1");else for(int i=1;i<=n;i++)printf("%d%c",find(i),"\n "[i<n]);
}
int main(){
	for(scanf("%d",&T);T--;get());return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
2 1
1 1
2 2
6 2
1 3
4 6
2 4
3 5
4 3
1 2
1 1
2 2
2 3
3 3
3 4

output:

-1
3 4 3 4 5 6
4 4 4 4

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 39ms
memory: 3804kb

input:

100000
2 1
1 1
2 2
2 1
2 2
1 2
2 1
1 2
2 2
2 1
1 2
2 2
2 1
2 2
1 2
2 1
2 2
1 1
2 1
1 1
2 2
2 1
1 2
2 2
2 1
2 2
1 1
2 1
2 2
1 2
2 1
2 2
1 1
2 1
2 2
1 2
2 1
2 2
1 2
2 1
2 2
1 1
2 1
2 2
1 1
2 1
1 2
2 2
2 1
2 2
1 2
2 1
2 2
1 2
2 1
2 2
1 2
2 1
1 1
2 2
2 1
2 2
1 2
2 1
1 1
2 2
2 1
1 1
2 2
2 1
2 2
1 2
2 1
2...

output:

-1
2 2
2 2
2 2
2 2
-1
-1
2 2
-1
2 2
-1
2 2
2 2
-1
-1
2 2
2 2
2 2
2 2
-1
2 2
-1
-1
2 2
-1
2 2
2 2
-1
-1
2 2
2 2
-1
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
-1
2 2
2 2
2 2
2 2
2 2
2 2
-1
2 2
2 2
2 2
2 2
-1
2 2
-1
2 2
2 2
2 2
2 2
2 2
2 2
2 2
-1
2 2
2 2
2 2
-1
-1
2 2
-1
2 2
2 2
-1
2 2
-1
2 2
2 2
-1
2 2
2 2
2 2
-...

result:

ok ok (100000 test cases)

Test #3:

score: -100
Wrong Answer
time: 48ms
memory: 3532kb

input:

25000
10 5
4 10
1 4
9 9
2 9
5 8
1 8
1 5
5 5
4 9
6 6
11 5
9 11
4 7
2 2
2 5
8 10
3 11
2 4
4 8
3 10
4 6
5 2
1 3
4 4
1 5
5 5
6 3
4 6
3 3
1 5
3 6
1 1
1 3
7 3
4 4
3 5
1 6
3 4
2 3
1 2
7 3
3 4
1 5
6 7
2 6
3 5
2 3
5 2
5 5
4 5
2 3
1 1
10 5
3 6
4 5
3 3
6 9
2 5
9 10
5 6
5 7
1 4
8 9
11 5
1 10
2 11
6 9
2 6
6 6
8 ...

output:

10 9 3 10 10 6 7 10 9 10
1 8 10 8 8 6 7 8 9 10 10
3 2 3 4 3
6 2 6 4 6 6
3 3 3 4 5 3 7
5 3 3 4 5 3 7
1 3 3 5 5
7 7 6 7 7 6 7 8 9 10
10 3 3 4 3 3 7 8 9 10 3
3 3 3 4 3 3 7 8
3 2 3 4 3 6 3 3 9 3
6 6 3 4 6 6 6 8
15 15 15 4 15 15 7 13 15 10 11 12 13 14 15 15 17
8 8 8 6 5 6 7 8 6 10 11 12 8
6 6 3 4 6 6
10 ...

result:

wrong answer the number of segments with two equal elements is 7 != 5 (test case 1)
English 繁體中文 简体中文

Server Time: 2024-12-02 12:59:39 | OpenSource Project