QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21701#2832. Graph Theoryjyyyyds#WA 44ms13248kbC++20698b2022-03-08 14:20:122022-05-08 03:57:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 03:57:50]
  • 评测
  • 测评结果：WA
  • 用时：44ms
  • 内存：13248kb
查看
  • [2022-03-08 14:20:12]
  • 提交

answer

#include<bits/stdc++.h>
#define N 200005

int n,m;

std::vector<int> A[N],B[N];

int main(){
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;i++)
			A[i].clear(),B[i].clear();
		std::multiset<int> s;
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			if(u>v)
				std::swap(u,v);
			s.insert(v-u);
			A[u].push_back(v);
		}
		int ans=*s.rbegin();
		for(int i=1;i<n;i++){
			for(auto j:A[i]){
				if(i==j)
					continue;
				int x=j-i;
				s.erase(s.find(x)),s.insert(n-x);
				B[j+1].push_back(i);
			}
			for(auto j:B[i]){
				int x=i-1-j;
				s.erase(s.find(n-x)),s.insert(x);
			}
			ans=std::min(ans,*s.rbegin());
		}
		printf("%d\n",ans);
	}
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 13180kb

input:

3 2
1 2
2 3
3 2
1 1
2 2
3 3
1 2
2 3
3 1

output:

1
0
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 13248kb

input:

2 1
1 2

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Wrong Answer
time: 44ms
memory: 13212kb

input:

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

output:

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

result:

wrong answer 2nd lines differ - expected: '6', found: '9'
English 繁體中文 简体中文

Server Time: 2024-11-30 05:52:57 | OpenSource Project