UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190936#3393. 酒店预定heyuzhen1001167ms11952kbC++111004b2023-10-07 19:12:002023-10-07 21:40:42

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,q,p[100005],x[100005][2],vis[100005],u,v,f[100005][2];
struct node{
	ll x,pos,f;
}now;
queue<node> que;
vector<ll> e[100005];
void bfs(){
	while(que.size()){
		now = que.front();
		que.pop();
		if(x[now.x][0] == -1)x[now.x][0] = now.pos,f[now.x][0] = now.f;
		else if(x[now.x][0] == now.pos)continue;
		else if(x[now.x][1] == -1)x[now.x][1] = now.pos,f[now.x][1] = now.f;
		else continue;
		ll u = now.x;
		for(ll i = 0;i < e[u].size();i++){
			ll v = e[u][i];
			que.push({v,now.pos,now.f + 1});
		}
	}
}
int main(){
	cin >> n >> m >> k >> q;
	memset(x,-1,sizeof x);
	for(ll i = 1;i <= k;i++){
		cin >> p[i];
		que.push({p[i],i,0});
	}for(ll i = m;i;i--){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}bfs();
	while(q--){
		cin >> u >> v;
		if(v == 0)cout << f[u][0] << "\n";
		else if(x[u][0] == v)cout << f[u][1] << "\n";
		else cout << f[u][0] << "\n";
	}return 0;
}
源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 5172kb

input:

8 10 3 10
2 6 4
3 7
5 7
1 3
3 6
5 4
6 8
7 1
5 8
5 3
1 2
6 1
1 0
1 1
7 3
5 0
4 2
7 3
8 3
2 3
7 3

output:

0
1
2
2
1
0
2
1
0
2

result:

ok 10 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 5168kb

input:

7 10 3 10
2 6 1
1 1
2 3
5 2
4 2
2 6
1 4
2 1
4 3
4 7
1 6
6 3
7 0
6 0
7 1
3 2
7 0
4 1
2 0
1 1
7 2

output:

0
2
0
2
1
2
1
0
0
2

result:

ok 10 lines

Test #3:

score: 10
Accepted
time: 0ms
memory: 5168kb

input:

7 10 3 10
3 6 2
6 5
4 7
1 6
1 4
7 1
1 5
6 2
3 4
7 5
7 1
3 0
2 1
6 2
2 2
7 2
4 2
7 0
3 0
1 0
3 0

output:

0
0
1
0
2
1
2
0
1
0

result:

ok 10 lines

Test #4:

score: 10
Accepted
time: 0ms
memory: 5252kb

input:

900 1000 100 1000
398 317 819 455 511 268 885 898 820 332 4 371 620 518 765 149 479 651 873 349 841 ...

output:

2
2
1
5
2
1
3
3
5
1
3
0
3
0
1
5
2
1
4
2
3
1
3
1
3
1
4
1
3
4
5
4
0
1
2
1
2
1
2
3
2
3
3
0
3
5
2
1
5
1
...

result:

ok 1000 lines

Test #5:

score: 10
Accepted
time: 0ms
memory: 5248kb

input:

900 1000 30 1000
849 378 50 402 389 341 4 119 745 416 374 790 48 694 230 245 823 798 44 532 860 454 ...

output:

1
2
1
5
6
4
3
2
7
3
4
5
3
2
3
4
3
1
4
6
6
5
5
4
2
7
3
3
5
6
5
4
3
2
2
5
3
6
1
4
6
4
3
2
3
4
2
3
4
4
...

result:

ok 1000 lines

Test #6:

score: 10
Accepted
time: 239ms
memory: 11356kb

input:

90000 100000 10 100000
31111 75890 6736 9695 42659 69478 50623 52606 35513 32914
60539 25277
1628 76...

output:

18
15
19
19
13
17
16
20
17
13
19
19
15
14
20
16
11
12
18
19
18
20
18
17
15
17
17
18
16
16
20
18
16
1...

result:

ok 100000 lines

Test #7:

score: 10
Accepted
time: 206ms
memory: 11884kb

input:

90000 100000 10 100000
18495 70286 60194 54197 4868 2994 84428 40746 71223 34775
74986 19884
78399 4...

output:

12
11
12
15
13
13
11
13
11
12
11
11
13
13
11
15
13
11
10
11
14
12
13
12
10
10
15
13
8
13
10
13
10
14...

result:

ok 100000 lines

Test #8:

score: 10
Accepted
time: 238ms
memory: 11884kb

input:

90000 100000 5000 100000
33728 73144 74729 28103 81177 5891 89573 64153 50169 88438 59204 69045 6256...

output:

4
3
8
2
5
6
3
0
4
0
4
4
4
1
6
2
3
2
11
3
1
5
8
5
2
3
2
1
0
6
4
4
5
4
5
2
2
4
3
1
4
2
1
5
4
2
5
4
3
5...

result:

ok 100000 lines

Test #9:

score: 10
Accepted
time: 230ms
memory: 11936kb

input:

90000 100000 5000 100000
1304 59969 6507 72591 23147 41247 28927 84683 22557 42648 88289 44535 65708...

output:

4
4
4
3
0
3
6
3
4
5
2
5
1
3
2
2
0
5
6
4
4
6
5
6
7
2
8
4
1
2
2
6
5
4
4
3
4
5
4
4
1
1
0
3
4
3
3
8
2
6
...

result:

ok 100000 lines

Test #10:

score: 10
Accepted
time: 254ms
memory: 11952kb

input:

90000 100000 5000 100000
44728 21517 19765 2068 32401 1512 60910 11375 66713 54126 71432 71575 58502...

output:

2
4
7
1
2
8
4
3
3
2
3
8
1
0
5
2
2
2
3
5
4
7
6
3
4
5
6
2
1
3
4
6
7
3
10
1
2
3
3
3
4
0
2
3
1
2
3
3
0
1...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-02-27 01:54:06 | 开源项目