QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#359771	#408. Dungeon 2	abc123	0	40ms	20148kb	C++20	2.4kb	2024-03-20 20:44:36	2024-03-20 20:44:37

Judging History

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

[2024-03-20 20:44:37]
评测

测评结果：0
用时：40ms
内存：20148kb

查看

[2024-03-20 20:44:36]
提交

answer

#include <bits/stdc++.h>
#include "dungeon2.h"
using namespace std;
#define pii pair<int,int>

vector<int> do_wym[203];
int known_deg[203];
vector<pii> graph[203];
vector<pii> sciezki[203][203];
int macierz[203][203];
int dp[203][203];
int wyn[203];
pii fat[203];
int deg[203];
int wolne=0;

void dfs(int v, int p){
	deg[v]=NumberOfRoads();
	do_wym[v].resize(deg[v]+1);
	if (v!=1){
		fat[v]={LastRoad(),p};
		do_wym[v][LastRoad()]=p;
		known_deg[v]++;
		graph[v].push_back({p,LastRoad()});
	}
	for (int i = 1; i<=deg[v]; i++){
		if (i==fat[v].first)continue;
		Move(i,2);
		if (Color()==2)Move(LastRoad(),2);
		else{
			do_wym[v][i]=++wolne;
			known_deg[v]++;
			graph[v].push_back({wolne,i});
			dfs(wolne,v);
		}
	}
	if (v!=1)Move(fat[v].first,2);
}

bool build_sciezka(int v, int p, int a, int b){
	if (v==b)return true;
	for (auto u : graph[v]){
		if (u.first==p)continue;
		sciezki[a][b].push_back(u);
		if (build_sciezka(u.first,v,a,b))return true;
		sciezki[a][b].pop_back();
	}
	return false;
}

void MyMove(int a, int b){
	for (auto u : sciezki[a][b]){
		Move(u.second,Color());
	}
}

void Inspect(int R){
	dfs(++wolne,0);
	int n=wolne;
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=n; j++){
			build_sciezka(i,0,i,j);
		}
	}
	int cur=1;
	for (int i = 1; i<=n; i++){
		if (known_deg[i]<deg[i]){
			MyMove(cur,i);
			cur=i;
			Move(1,3);
			Move(LastRoad(),1);
			for (int j = i+1; j<=n; j++){
				if (known_deg[j]<deg[j]){
					MyMove(cur,j);
					cur=j;
					for (int u = 1; u<=deg[cur] && known_deg[cur]<deg[cur]; u++){
						Move(u,1);
						if (Color()==3){
							known_deg[i]++;
							known_deg[j]++;
							macierz[i][j]=macierz[j][i]=1;
						}
						Move(LastRoad(),Color());
					}
				}
			}
			MyMove(cur,i);
			cur=i;
			Move(1,1);
			Move(LastRoad(),1);
		}
	}
	for (int i = 1; i<=n; i++){
		for (auto u : graph[i])macierz[i][u.first]=macierz[u.first][i]=1;
	}
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=n; j++){
			dp[i][j]=1000;
			if (i==j)dp[i][j]=0;
			if (macierz[i][j])dp[i][j]=macierz[i][j];
		}
	}
	for (int k = 1; k<=n; k++){
		for (int i = 1; i<=n; i++){
			for (int j = 1; j<=n; j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	for (int i = 1; i<=n; i++){
		for (int j = i+1; j<=n; j++){
			wyn[dp[i][j]]++;
		}
	}
	for (int i = 1; i<=R; i++){
		Answer(i,wyn[i]);
	}
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0

Runtime Error

Test #1:

score: 17

Accepted

time: 1ms

memory: 4016kb

input:

10 100 50
7
5 7 10 4 6 2 3
2
1 5
3
1 10 7
2
10 1
3
1 9 2
2
1 7
5
9 6 8 3 1
1
7
2
5 7
3
1 4 3
15
24
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

output:

Accepted: #move = 84

result:

ok

Test #2:

score: 0

Accepted

time: 2ms

memory: 4592kb

input:

50 100 50
2
39 10
4
7 43 11 33
2
7 18
1
14
3
46 42 27
2
12 49
4
2 41 3 35
1
37
1
14
4
13 14 19 1
3
22 2 44
1
6
4
49 21 10 36
6
4 9 35 10 37 20
1
49
2
21 29
2
45 25
2
3 28
2
10 38
2
50 14
2
16 13
1
11
1
38
1
41
1
17
2
48 32
3
40 5 48
1
18
1
16
1
49
1
40
1
26
1
2
1
50
2
7 14
1
13
2
8 14
2
23 19
2
45 1...

output:

Accepted: #move = 124

result:

ok

Test #3:

score: 0

Accepted

time: 0ms

memory: 4528kb

input:

50 100 10
2
4 41
1
33
3
25 27 13
2
30 1
4
28 11 8 22
2
36 39
1
10
1
5
2
35 30
2
35 7
2
32 5
1
26
3
49 21 3
4
19 29 20 22
1
23
1
49
2
18 42
2
50 17
1
14
1
14
2
22 13
3
5 14 21
2
28 15
2
29 36
2
3 34
3
12 31 34
1
3
2
5 23
4
24 38 14 40
5
4 45 33 9 39
2
38 26
2
48 11
2
2 30
3
46 25 26
2
9 10
2
6 24
1
5...

output:

Accepted: #move = 196

result:

ok

Test #4:

score: 0

Accepted

time: 2ms

memory: 4604kb

input:

50 100 50
3
5 16 18
1
43
4
46 14 31 38
3
34 22 39
2
1 33
2
12 30
2
41 24
2
29 23
2
45 47
2
15 40
3
50 42 43
2
19 6
2
40 22
3
3 39 22
2
19 10
1
1
1
47
1
1
2
15 12
1
35
2
27 48
3
14 4 13
3
26 39 8
1
7
3
26 29 33
2
23 25
1
21
3
35 40 36
2
25 8
1
6
2
3 42
1
46
3
5 43 25
2
40 4
2
20 28
1
28
1
40
1
3
4
4 ...

output:

Accepted: #move = 300

result:

ok

Test #5:

score: -17

Runtime Error

input:

50 100 50
2
11 48
2
25 22
2
7 30
1
40
2
50 37
1
34
3
15 36 3
3
42 21 33
3
10 32 27
2
45 9
3
1 18 32
4
36 13 34 43
4
43 18 21 12
1
45
3
7 31 28
3
50 18 22
2
28 20
4
11 22 13 16
1
50
2
29 17
3
8 13 43
5
2 35 16 18 27
2
36 24
1
23
2
2 26
2
25 41
2
9 22
2
17 15
3
49 20 30
3
3 38 29
2
15 49
3
9 11 39
1
8...

output:

Wrong Answer [4]

result:

Subtask #2:

score: 0

Runtime Error

Test #16:

score: 27

Accepted

time: 0ms

memory: 3948kb

input:

output:

Accepted: #move = 125

result:

ok

Test #17:

score: 0

Accepted

time: 2ms

memory: 4452kb

input:

50 3 50
1
5
1
42
3
48 14 28
1
23
3
36 22 1
2
44 14
3
38 14 26
1
37
2
24 45
2
40 42
1
37
1
33
3
21 23 49
4
3 7 47 6
3
41 39 24
2
40 18
1
38
1
16
1
30
1
22
1
13
3
5 20 28
2
13 4
4
28 37 15 9
1
30
2
7 50
2
30 47
3
24 22 3
3
32 47 40
3
19 27 25
3
35 37 44
3
43 29 33
2
12 32
1
37
1
31
1
5
6
34 46 31 8 24...

output:

Accepted: #move = 129

result:

ok

Test #18:

score: 0

Accepted

time: 2ms

memory: 4640kb

input:

50 3 10
2
28 25
3
23 30 25
3
6 10 46
1
47
1
39
2
3 29
2
28 24
3
41 42 45
1
21
1
3
2
33 38
2
50 38
2
44 17
2
41 31
2
23 20
1
48
4
37 21 50 13
1
49
2
41 31
1
15
2
17 9
1
24
4
48 40 2 15
2
7 22
2
2 1
3
39 30 27
2
36 26
2
7 1
3
6 43 30
5
47 29 26 42 2
2
19 14
1
39
2
41 11
1
39
1
43
1
27
1
17
3
11 49 12
...

output:

Accepted: #move = 172

result:

ok

Test #19:

score: -27

Runtime Error

input:

50 3 50
1
48
2
38 42
2
19 27
1
13
1
46
3
39 34 13
1
50
2
27 22
2
14 39
3
46 40 43
2
12 15
2
11 21
3
44 4 6
2
9 28
1
11
2
27 25
2
42 27
3
24 21 50
3
20 3 32
3
41 19 26
4
43 18 36 12
3
45 44 8
2
42 45
1
18
2
16 35
1
20
5
29 8 3 16 17
3
44 49 14
1
27
1
40
1
50
1
19
1
49
2
6 36
1
25
2
34 21
1
42
1
2
3
6...

output:

Wrong Answer [4]

result:

Subtask #3:

score: 0

Runtime Error

Test #31:

score: 56

Accepted

time: 40ms

memory: 20148kb

input:

200 3 200
6
149 79 143 164 179 68
4
44 52 144 113
1
84
3
31 188 166
1
109
4
154 192 125 147
1
198
4
103 27 192 95
3
33 166 179
1
125
3
31 61 150
3
168 152 161
2
67 64
1
136
2
150 17
1
192
2
15 142
2
56 122
1
35
2
97 200
2
129 22
4
72 134 31 21
2
53 82
4
195 181 104 146
1
78
1
88
3
8 78 127
4
152 200...

output:

Accepted: #move = 1687

result:

points 1.0 L = 8.033333333333

Test #32:

score: 0

Runtime Error

input:

200 3 200
8
149 79 143 164 179 68 5 54
4
44 52 113 144
2
152 84
3
166 188 31
3
1 149 109
6
125 192 140 147 154 182
1
198
6
29 103 95 27 192 44
3
166 33 179
5
105 189 125 120 79
3
150 61 31
5
161 179 152 168 186
3
124 67 64
2
136 104
2
17 150
2
93 192
3
142 21 15
5
122 47 56 62 29
1
35
2
97 200
4
22 ...

output:

Wrong Answer [4]