QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114022#6629. Travelling Trader1kri7 14ms16028kbC++146.6kb2023-06-20 15:32:542023-06-20 15:32:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-20 15:32:55]
  • 评测
  • 测评结果：7
  • 用时：14ms
  • 内存：16028kb
查看
  • [2023-06-20 15:32:54]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;
int n,k,u[400005],v[400005],first[200005],nxt[400005];
int a[200005];
namespace QwQ1{
	ll f[200005];
	int tot,id[200005];
	void dfs1(int now,int fa){
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa){
				dfs1(v[i],now);
				f[now]=max(f[now],f[v[i]]);
			}
		f[now]+=a[now];
		return;
	}
	void dfs2(int now,int fa){
		id[++tot]=now;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa&&f[now]==a[now]+f[v[i]]){
				dfs2(v[i],now);
				break;
			}
		return;
	}
	void work(){
		dfs1(1,0);
		dfs2(1,0);
		printf("%lld\n",f[1]);
		printf("%d\n",tot);
		for (int i=1;i<=tot;i++)printf("%d ",id[i]);
		printf("\n");
		return;
	}
}
namespace QwQ2{
	ll f0[200005],f1[200005],g0[200005],g1[200005];
	int id0[3][200005],id1[3][200005];
	void dfs1(int now,int fa){
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa)dfs1(v[i],now);
		vector<int> c;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa)c.push_back(v[i]);
		c.push_back(0),c.push_back(0);
		int len=c.size();
		ll sum=0;
		for (int i=0;i<len;i++)sum+=a[c[i]];
		for (int i=0;i<len;i++){
			id0[0][i]=id0[1][i]=0;
			if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
			if (id0[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
			if (id0[1][i]==-1||f0[c[i]]-a[c[i]]>f0[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
		}
		for (int t=1;t<len;t++){
			int x,y;
			x=id0[0][t-1],y=c[t];
			f0[now]=max(f0[now],g1[x]-a[x]+f0[y]-a[y]);
			x=c[t],y=id0[1][t-1];
			f0[now]=max(f0[now],g1[x]-a[x]+f0[y]-a[y]);
		}
		for (int i=0;i<len;i++)
			for (int j=0;j<len;j++){
				for (int k=0;k<len;k++){
					if (i!=j&&i!=k&&j!=k)
						f0[now]=max(f0[now],g1[c[i]]-a[c[i]]+g0[c[j]]-a[c[j]]+f1[c[k]]-a[c[k]]);
				}
			}
		f0[now]+=a[now]+sum;
		for (int i=0;i<len;i++){
			id0[0][i]=id0[1][i]=0;
			if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
			if (id0[0][i]==-1||g0[c[i]]-a[c[i]]>g0[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
			if (id0[1][i]==-1||f1[c[i]]-a[c[i]]>f1[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
		}
		for (int t=1;t<len;t++){
			int x,y;
			x=id0[0][t-1],y=c[t];
			f1[now]=max(f1[now],g0[x]-a[x]+f1[y]-a[y]);
			x=c[t],y=id0[1][t-1];
			f1[now]=max(f1[now],g0[x]-a[x]+f1[y]-a[y]);
		}
		f1[now]+=a[now]+sum;
		for (int i=0;i<len;i++)
			f1[now]=max(f1[now],a[now]+f0[c[i]]);
		for (int i=0;i<len;i++)g0[now]=max(g0[now],g1[c[i]]-a[c[i]]);
		g0[now]+=a[now]+sum;
		for (int i=0;i<len;i++)g1[now]=max(g1[now],g0[c[i]]-a[c[i]]);
		g1[now]+=a[now]+sum;
		return;
	}
	int tot,id[200005];
	void dfs2(int now,int fa,int o){
		vector<int> c;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa)c.push_back(v[i]);
		c.push_back(0),c.push_back(0);
		int len=c.size();
		ll sum=0;
		for (int i=0;i<len;i++)sum+=a[c[i]];
		if (o==0){
			for (int i=0;i<len;i++){
				id0[0][i]=id0[1][i]=0;
				if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
				if (id0[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
				if (id0[1][i]==-1||f0[c[i]]-a[c[i]]>f0[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
			}
			int x=-1,y=-1,z=-1;
			for (int t=1;t<len;t++){
				int _x,_y;
				_x=id0[0][t-1],_y=c[t];
				if (f0[now]==a[now]+sum+g1[_x]-a[_x]+f0[_y]-a[_y])x=_x,y=_y;
				_x=c[t],_y=id0[1][t-1];
				if (f0[now]==a[now]+sum+g1[_x]-a[_x]+f0[_y]-a[_y])x=_x,y=_y;
			}
			if (x!=-1&&y!=-1){
				for (int i=0;i<len;i++)
					if (c[i]!=x&&c[i]!=y&&c[i]!=0)id[++tot]=c[i];
				if (x!=0)dfs2(x,now,3);
				id[++tot]=now;
				if (y!=0)dfs2(y,now,0);
				return;
			}
			for (int i=0;i<len;i++)
				for (int j=0;j<len;j++){
					for (int k=0;k<len;k++){
						if (i!=j&&i!=k&&j!=k)
							if (f0[now]==a[now]+sum+g1[c[i]]-a[c[i]]+g0[c[j]]-a[c[j]]+f1[c[k]]-a[c[k]]){
								for (int l=0;l<len;l++)
									if (c[l]!=c[i]&&c[l]!=c[j]&&c[l]!=c[k]&&c[l]!=0)id[++tot]=c[l];
								if (c[i]!=0)dfs2(c[i],now,3);
								id[++tot]=now;
								if (c[j]!=0)dfs2(c[j],now,2);
								if (c[k]!=0)dfs2(c[k],now,1);
								return;
							}
					}
				}
			return;
		}
		if (o==1){
			id[++tot]=now;
			for (int i=0;i<len;i++){
				id0[0][i]=id0[1][i]=0;
				if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
				if (id0[0][i]==-1||g0[c[i]]-a[c[i]]>g0[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
				if (id0[1][i]==-1||f1[c[i]]-a[c[i]]>f1[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
			}
			int x=-1,y=-1;
			for (int t=1;t<len;t++){
				int _x,_y;
				_x=id0[0][t-1],_y=c[t];
				if (f1[now]==a[now]+sum+g0[_x]-a[_x]+f1[_y]-a[_y])x=_x,y=_y;
				_x=c[t],_y=id0[1][t-1];
				if (f1[now]==a[now]+sum+g0[_x]-a[_x]+f1[_y]-a[_y])x=_x,y=_y;
			}
			if (x!=-1&&y!=-1){
				if (x!=0)dfs2(x,now,2);
				for (int i=0;i<len;i++)
					if (c[i]!=x&&c[i]!=y&&c[i]!=0)id[++tot]=c[i];
				if (y!=0)dfs2(y,now,1);
				return;
			}
			for (int i=0;i<len;i++)
				if (f1[now]==a[now]+f0[c[i]]){
					dfs2(c[i],now,0);
					return;
				}
			return;
		}
		if (o==2){
			int qwq=0;
			for (int i=0;i<len;i++)
				if (g0[now]==a[now]+g1[c[i]]+sum-a[c[i]])qwq=c[i];
			for (int i=0;i<len;i++)
				if (c[i]!=qwq&&c[i]!=0)id[++tot]=c[i];
			if (qwq!=0)dfs2(qwq,now,3);
			id[++tot]=now;
			return;
		}
		if (o==3){
			id[++tot]=now;
			int qwq=0;
			for (int i=0;i<len;i++)
				if (g1[now]==a[now]+g0[c[i]]+sum-a[c[i]])qwq=c[i];
			if (qwq!=0)dfs2(qwq,now,2);
			for (int i=0;i<len;i++)
				if (c[i]!=qwq&&c[i]!=0)id[++tot]=c[i];
			return;
		}
		return;
	}
	void work(){
		dfs1(1,0);
		dfs2(1,0,1);
		printf("%lld\n",f1[1]);
		printf("%d\n",tot);
		for (int i=1;i<=tot;i++)printf("%d ",id[i]);
		printf("\n");
		return;
	}
}
namespace QwQ3{
	void dfs1(int,int);
	void dfs2(int,int);
	int tot,id[200005];
	void dfs2(int now,int fa){
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa)dfs1(v[i],now);
		id[++tot]=now;
		return;
	}
	void dfs1(int now,int fa){
		id[++tot]=now;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa)dfs2(v[i],now);
		return;
	}
	void work(){
		dfs1(1,0);
		ll sum=0;
		for (int i=1;i<=n;i++)sum+=a[i];
		printf("%lld\n",sum);
		printf("%d\n",tot);
		for (int i=1;i<=tot;i++)printf("%d ",id[i]);
		printf("\n");
		return;
	}
}
int main(){
	scanf("%d%d",&n,&k);
	assert(k==2);
	for (int i=1;i<n;i++){
		scanf("%d%d",&u[i],&v[i]);
		nxt[i]=first[u[i]],first[u[i]]=i;
		u[i+n]=v[i],v[i+n]=u[i];
		nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
	}
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	if (k==1){
		QwQ1::work();
		return 0;
	}
	if (k==2){
		QwQ2::work();
		return 0;
	}
	if (k==3){
		QwQ3::work();
		return 0;
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

2 1
1 2
255959470 961356354

output:

result:

Subtask #2:

score: 7
Accepted

Test #12:

score: 7
Accepted
time: 1ms
memory: 13948kb

input:

2 2
2 1
243296356 635616793

output:

878913149
2
1 2

result:

ok correct!

Test #13:

score: 0
Accepted
time: 1ms
memory: 13964kb

input:

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

output:

33
10
1 4 10 3 9 7 5 6 2 8

result:

ok correct!

Test #14:

score: 0
Accepted
time: 1ms
memory: 9916kb

input:

200 2
150 170
21 33
96 152
143 26
136 70
92 159
34 164
163 182
74 115
93 61
151 83
81 119
10 146
114 170
39 83
139 4
173 41
193 96
87 57
14 164
107 51
45 15
157 17
43 183
96 30
11 137
55 18
138 81
87 12
112 122
159 82
195 185
75 71
16 191
33 88
70 195
149 114
106 160
96 118
92 44
9 141
107 143
151 2...

output:

57921623677
100
1 135 89 194 179 151 39 83 27 40 112 125 180 120 117 122 72 99 33 131 105 96 114 171 28 110 149 59 170 193 138 94 162 88 21 45 129 25 78 62 127 36 199 15 12 76 70 53 159 17 178 24 44 41 67 173 116 42 186 92 32 5 101 197 82 121 198 29 87 64 93 19 126 8 141 37 100 3 9 52 108 61 54 137 ...

result:

ok correct!

Test #15:

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

input:

200 2
33 5
171 115
70 64
38 42
123 154
167 183
152 177
36 102
98 116
125 187
61 148
143 136
62 169
102 142
86 189
115 100
85 172
136 50
158 113
133 5
10 108
90 178
90 21
127 28
122 189
115 18
83 109
197 11
53 70
191 141
166 90
70 9
74 148
160 7
186 151
197 86
147 82
107 161
122 140
110 58
179 25
107...

output:

47106979559
87
1 111 51 7 130 67 160 52 20 138 126 127 48 62 189 70 65 156 9 76 155 196 36 80 53 64 110 175 193 135 177 78 24 5 133 33 149 152 58 13 119 117 106 184 191 73 88 154 139 174 59 170 27 4 123 141 120 145 167 34 15 146 50 143 136 183 39 108 118 10 129 37 115 95 66 100 165 71 171 18 40 47 1...

result:

ok correct!

Test #16:

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

input:

200 2
139 197
14 69
160 138
115 60
1 141
176 33
94 88
108 26
106 20
96 60
126 180
171 110
140 91
138 63
57 183
42 62
126 163
126 64
87 167
22 142
190 112
27 120
187 109
83 111
23 196
95 47
105 177
96 170
192 113
136 188
24 198
116 137
53 177
178 38
30 158
125 64
123 132
36 114
77 192
125 165
194 7
9...

output:

73032451334
133
1 141 7 50 194 75 65 124 53 105 177 139 122 134 46 16 14 197 114 99 83 193 22 67 120 70 51 175 32 107 101 36 15 90 43 189 146 91 191 144 95 172 73 45 174 167 87 159 109 81 4 25 140 199 2 198 82 170 60 42 121 157 78 184 155 182 54 186 62 96 158 24 165 3 136 17 10 127 143 39 188 149 12...

result:

ok correct!

Test #17:

score: 0
Accepted
time: 2ms
memory: 9952kb

input:

200 2
182 43
15 179
37 173
45 38
62 4
131 151
83 188
84 58
183 148
155 59
141 133
128 19
191 170
129 87
67 156
120 199
94 11
162 27
175 86
73 50
143 94
81 103
84 120
12 19
59 38
48 34
127 41
196 87
135 69
43 119
54 176
180 112
89 60
67 117
149 18
53 61
12 1
46 67
25 38
8 52
119 51
162 197
12 31
166 ...

output:

63859058076
111
1 31 12 30 158 19 189 180 29 36 66 85 112 124 128 151 69 18 3 25 45 59 179 15 5 7 33 65 171 155 38 187 4 181 22 144 140 91 192 54 111 165 136 184 26 191 120 58 70 84 118 170 56 122 90 196 182 119 63 167 64 160 88 80 51 43 60 123 76 8 93 87 83 20 57 47 94 44 163 132 95 143 11 127 129 ...

result:

ok correct!

Test #18:

score: 0
Accepted
time: 1ms
memory: 14064kb

input:

200 2
12 76
61 106
151 109
163 180
11 135
109 179
35 199
86 104
82 109
80 70
15 123
180 154
134 91
187 81
167 4
27 71
174 101
124 127
154 29
173 175
172 61
59 109
53 55
76 55
174 67
50 169
180 32
1 182
126 3
148 146
58 127
26 181
189 47
10 156
120 112
157 149
136 166
146 122
59 17
99 136
55 138
49 1...

output:

59693686065
120
1 116 186 108 104 86 183 87 102 58 47 146 177 148 122 60 190 189 46 48 88 44 112 196 50 25 97 169 107 114 120 101 192 14 176 178 98 180 29 119 154 2 32 163 79 5 57 197 24 158 138 76 53 159 41 55 128 143 156 59 74 164 89 65 9 28 139 135 155 51 142 167 18 90 100 38 16 4 42 36 199 11 92...

result:

ok correct!

Test #19:

score: 0
Accepted
time: 2ms
memory: 9892kb

input:

200 2
33 83
16 197
177 12
71 47
85 60
34 49
96 78
30 39
63 122
95 17
168 74
89 83
62 134
45 166
48 6
178 91
151 72
153 47
104 174
86 140
33 134
24 51
129 71
48 94
141 93
64 118
155 50
43 28
182 92
31 142
105 56
156 100
83 69
179 90
140 127
186 148
16 47
175 4
123 173
27 50
154 186
107 98
200 20
66 6...

output:

61122293114
124
1 173 123 101 27 152 155 55 50 190 6 195 11 94 149 165 180 59 153 71 16 102 125 58 163 126 197 47 111 172 48 122 181 68 26 37 96 187 22 135 65 41 124 53 88 63 174 104 15 106 28 52 113 85 107 31 75 12 151 185 72 13 44 42 90 177 98 60 21 43 116 87 103 112 69 89 33 139 14 8 67 20 196 16...

result:

ok correct!

Test #20:

score: 0
Accepted
time: 0ms
memory: 9820kb

input:

200 2
91 28
137 24
181 33
82 19
90 182
180 77
2 6
190 176
100 181
13 140
52 77
85 189
28 29
176 22
7 180
55 176
99 113
6 93
28 51
117 44
180 127
114 174
102 92
13 14
129 181
80 24
95 28
181 195
162 4
28 188
55 162
59 131
47 45
145 176
136 197
145 57
159 117
143 106
192 106
126 28
43 23
51 73
109 28
...

output:

48771917800
98
1 79 64 109 188 95 51 29 91 126 166 21 135 113 26 99 46 103 104 40 130 36 28 198 172 63 13 62 133 11 117 12 97 145 55 22 190 93 30 17 65 84 81 102 59 37 131 92 8 136 151 24 6 176 158 69 155 160 90 82 106 50 125 165 49 192 143 19 129 48 23 43 71 78 41 67 132 199 96 25 181 180 156 76 14...

result:

ok correct!

Test #21:

score: 0
Accepted
time: 0ms
memory: 13980kb

input:

200 2
117 30
120 159
129 100
29 57
57 71
96 72
53 153
171 96
138 197
13 72
142 74
64 85
148 150
145 106
190 23
198 177
58 127
163 67
32 183
26 155
94 159
170 70
12 181
13 24
157 116
163 40
126 76
195 193
92 9
4 113
196 135
196 154
110 56
79 196
50 14
68 46
143 36
131 50
46 2
179 160
92 31
61 3
169 9...

output:

70064073402
147
1 197 165 18 6 98 168 180 136 122 47 167 121 103 48 138 123 104 163 73 162 81 67 161 21 174 189 119 145 170 16 193 93 175 8 141 76 63 34 159 105 44 143 172 65 36 82 94 200 126 137 155 195 70 75 106 85 91 43 190 133 148 97 41 125 56 110 111 150 140 160 23 64 37 144 128 100 7 182 157 1...

result:

ok correct!

Test #22:

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

input:

200 2
29 106
175 25
175 87
144 67
51 68
118 71
184 165
74 86
127 64
12 68
180 186
53 164
193 64
144 98
106 122
44 144
178 144
144 94
17 64
106 89
199 1
64 108
28 61
39 199
106 28
23 148
69 106
66 74
164 68
92 185
144 68
78 143
168 126
148 196
72 9
74 160
106 128
63 148
121 178
157 68
72 148
104 144
...

output:

64091222931
110
1 84 80 39 199 8 64 167 182 115 97 175 103 50 47 16 74 18 111 165 92 134 169 26 143 81 151 96 37 140 31 104 94 178 44 98 67 106 48 188 65 200 20 172 71 118 36 158 40 101 190 75 129 3 146 128 69 28 89 122 29 144 141 54 123 112 177 42 82 137 83 145 157 12 51 164 5 53 68 148 19 130 155 ...

result:

ok correct!

Test #23:

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

input:

200 2
161 12
189 84
46 61
69 75
139 170
146 21
162 91
20 125
40 78
152 25
81 140
15 138
39 184
85 183
29 59
166 126
127 24
125 56
94 26
92 37
33 196
168 16
75 64
148 57
112 142
185 46
49 195
76 18
88 79
70 125
194 136
12 154
77 195
10 2
86 155
90 170
83 67
38 179
172 175
198 191
11 51
67 42
25 93
18...

output:

82840243479
163
1 151 57 165 147 148 60 17 97 110 198 121 191 101 143 71 152 134 46 100 33 131 192 116 173 31 185 61 25 52 5 93 99 114 98 43 197 200 80 169 183 85 177 132 19 13 117 188 14 140 39 8 75 161 154 72 180 35 66 133 164 199 174 68 55 12 69 64 144 81 21 146 74 84 79 9 182 7 88 189 37 145 92 ...

result:

ok correct!

Test #24:

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

input:

200 2
19 106
54 55
83 185
106 178
78 194
51 66
133 200
106 58
106 35
163 150
50 104
96 105
124 105
41 66
124 22
54 106
27 93
106 133
196 124
58 83
106 193
124 110
194 165
150 124
194 13
42 149
127 154
121 159
106 26
100 181
124 82
1 80
177 45
69 100
54 189
61 19
70 106
134 175
168 134
6 112
44 100
1...

output:

60321563038
110
1 154 31 45 46 6 114 191 188 84 56 174 180 195 113 98 128 167 12 182 93 138 40 155 70 26 193 133 54 35 58 178 19 100 161 81 140 36 68 141 121 159 38 87 101 104 158 8 143 152 198 173 190 88 148 145 44 69 181 106 10 29 71 116 90 142 111 57 13 165 78 156 194 124 109 117 136 199 153 144 ...

result:

ok correct!

Test #25:

score: 0
Accepted
time: 0ms
memory: 9884kb

input:

200 2
104 32
163 164
138 166
140 114
144 134
193 184
94 25
196 140
119 160
29 34
170 7
175 60
122 185
85 133
9 53
95 89
171 158
34 155
67 32
73 125
167 128
27 48
157 119
105 2
13 142
134 120
71 118
66 117
182 59
156 43
84 91
126 80
55 192
34 68
64 194
131 75
81 151
117 102
145 104
99 4
3 65
91 35
79...

output:

80439812057
153
1 136 65 3 44 109 45 71 4 69 79 99 118 167 128 41 88 165 64 194 14 93 73 163 43 58 156 108 62 176 164 133 49 197 125 178 25 94 182 123 59 115 19 144 89 74 146 53 196 114 147 137 15 8 169 154 57 127 140 189 134 185 103 80 51 188 175 172 170 121 75 26 38 171 158 162 100 184 131 46 7 60...

result:

ok correct!

Test #26:

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

input:

200 2
105 64
190 149
84 15
184 93
52 80
182 129
160 51
108 184
105 167
9 77
61 80
109 84
161 188
121 2
121 20
175 60
80 154
105 88
25 60
88 10
41 123
105 135
99 184
100 98
152 105
1 75
184 199
163 102
63 88
56 184
83 13
101 123
107 50
120 42
8 78
105 45
105 121
184 92
105 129
136 124
123 139
88 19
7...

output:

51611310581
104
1 33 5 75 60 51 159 136 189 127 130 50 141 165 172 161 86 84 198 106 102 147 27 46 57 129 121 45 152 135 88 167 64 123 14 72 144 181 166 68 177 143 193 185 113 77 155 90 96 139 101 41 105 190 32 97 174 74 8 26 162 17 104 4 128 16 111 31 85 30 67 114 98 154 61 52 176 12 200 80 184 40 ...

result:

ok correct!

Test #27:

score: 0
Accepted
time: 14ms
memory: 13988kb

input:

200 2
8 1
1 22
39 1
168 1
136 1
197 1
1 142
1 4
18 1
187 1
1 74
156 1
1 94
118 1
1 86
1 76
30 1
52 1
1 42
144 1
105 1
64 1
1 9
137 1
112 1
101 1
75 1
1 113
1 164
1 29
1 60
1 167
1 135
1 192
196 1
48 1
1 179
170 1
158 1
1 145
47 1
1 98
143 1
184 1
84 1
72 1
20 1
109 1
1 106
1 3
1 79
55 1
1 77
102 1
1...

output:

89576768884
200
1 27 129 53 66 131 95 182 10 19 34 99 171 191 89 169 178 83 45 88 65 92 150 33 124 134 51 50 44 183 21 35 91 157 190 87 57 97 188 14 155 200 32 16 67 185 172 140 78 58 62 193 165 139 110 100 152 104 2 68 117 119 80 56 111 71 174 61 13 36 141 132 123 90 69 149 108 122 116 82 43 180 15...

result:

ok correct!

Test #28:

score: 0
Accepted
time: 5ms
memory: 13900kb

input:

199 2
1 106
198 165
176 34
59 39
1 34
151 36
78 85
1 109
48 4
1 13
165 1
73 163
159 126
150 106
1 33
82 103
17 180
1 151
46 87
1 111
195 1
1 164
25 23
135 161
1 107
1 2
11 58
97 1
170 1
71 57
72 157
1 158
1 186
153 1
1 60
29 1
27 52
50 1
162 122
64 1
95 1
1 75
160 142
134 81
77 155
79 1
1 119
30 169...

output:

101902858721
102
1 121 181 49 87 110 154 115 68 192 147 59 86 196 94 38 185 114 145 149 138 70 71 131 84 80 177 125 93 56 190 91 162 89 23 76 20 137 69 140 67 136 134 193 52 96 169 112 78 160 118 163 174 180 48 18 99 171 126 161 184 103 45 83 141 168 35 144 90 77 183 128 132 120 157 119 79 75 95 64 ...

result:

ok correct!

Test #29:

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

input:

197 2
24 1
65 24
129 58
92 96
61 1
42 18
95 3
167 168
147 110
2 172
143 156
115 110
1 67
158 127
99 134
126 89
30 95
85 13
1 149
128 106
81 118
137 100
146 88
105 1
76 105
153 9
96 123
67 49
61 186
1 9
120 46
51 79
79 1
77 195
17 11
117 7
114 106
135 21
59 1
100 122
179 67
158 184
16 83
96 1
191 75
...

output:

55959842378
56
1 181 78 133 23 161 95 90 195 162 106 40 21 99 36 118 2 187 197 7 58 182 108 17 46 167 29 53 16 169 13 188 93 88 143 42 158 126 75 100 10 110 121 96 59 79 9 105 149 67 61 24 32 163 107 97

result:

ok correct!

Test #30:

score: 0
Accepted
time: 2ms
memory: 9972kb

input:

196 2
83 40
1 26
46 179
44 181
73 123
46 128
150 168
150 151
134 48
91 48
47 79
161 46
114 35
120 35
183 48
47 66
154 69
150 45
74 40
32 63
48 1
22 18
41 26
1 46
78 47
88 40
152 47
191 44
60 46
57 48
67 73
150 38
48 10
126 89
44 23
44 56
31 126
196 150
80 35
46 25
129 32
20 22
75 44
73 145
170 154
2...

output:

26055322292
42
1 189 106 102 2 111 37 8 5 193 54 65 158 129 63 32 40 73 47 44 22 35 126 154 46 48 26 150 124 109 115 15 104 166 98 135 93 196 38 45 151 168

result:

ok correct!

Test #31:

score: 0
Accepted
time: 1ms
memory: 9948kb

input:

200 2
119 95
47 18
176 194
73 36
90 105
24 29
79 39
53 98
130 111
42 125
158 15
100 60
128 149
76 41
134 1
108 2
94 157
196 43
145 100
11 9
144 175
37 40
5 120
49 117
165 134
158 84
142 51
82 167
157 108
175 161
50 22
177 35
95 118
77 116
33 131
194 27
116 128
189 72
28 192
130 112
26 4
187 121
97 4...

output:

200000000000
200
1 134 165 110 89 187 121 78 61 122 9 11 173 186 56 30 20 74 69 168 6 93 198 12 191 144 175 161 32 79 39 8 27 194 176 113 148 10 52 150 181 124 99 57 73 36 13 88 192 28 23 183 15 158 84 70 71 166 188 151 140 169 98 53 64 139 43 196 50 22 87 54 156 162 109 189 72 199 159 179 25 40 37 ...

result:

ok correct!

Test #32:

score: 0
Accepted
time: 0ms
memory: 11924kb

input:

200 2
7 176
162 197
197 66
22 23
177 157
49 22
65 171
119 124
155 193
15 41
34 105
61 102
126 31
36 195
14 192
173 57
75 4
104 174
141 20
185 123
199 145
18 9
110 200
148 9
90 137
35 19
106 139
150 172
91 47
168 180
104 70
169 200
161 66
129 114
66 118
71 200
160 133
31 196
36 11
195 49
112 51
22 15...

output:

99918618520
200
1 189 171 65 102 165 61 24 199 191 145 183 34 105 90 81 137 56 172 150 124 40 119 68 170 76 72 74 73 135 36 11 195 6 49 198 22 151 23 55 188 94 47 109 91 149 60 159 173 77 57 154 19 35 120 83 86 52 114 129 63 13 106 33 139 89 133 108 160 184 103 100 194 37 38 134 193 155 152 136 64 2...

result:

ok correct!

Test #33:

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

input:

200 2
108 103
141 45
176 16
96 38
130 106
18 176
61 23
38 22
154 198
83 123
77 52
102 188
133 125
123 116
120 45
164 195
174 48
163 54
74 31
199 175
79 110
137 173
182 153
22 1
65 54
60 16
187 144
45 188
99 152
17 118
64 118
75 163
74 141
181 184
39 175
172 117
118 100
138 164
172 99
52 162
200 80
1...

output:

97817235416
200
1 72 6 131 22 3 76 55 38 135 111 96 48 192 112 66 174 14 85 68 23 2 127 61 99 37 149 152 172 40 168 117 19 57 63 193 144 178 78 187 180 122 165 84 62 15 151 47 200 166 114 80 16 160 128 60 176 24 169 18 73 105 90 93 134 5 177 58 103 10 179 108 133 159 97 125 139 98 183 140 118 100 64...

result:

ok correct!

Test #34:

score: 0
Accepted
time: 2ms
memory: 11980kb

input:

200 2
185 93
20 134
91 82
108 129
123 164
104 56
146 113
110 5
83 87
106 63
67 199
41 108
114 133
172 99
57 132
46 199
32 45
170 191
123 200
53 141
124 186
44 162
65 159
85 195
196 19
7 134
64 35
88 58
23 28
30 20
76 11
176 167
36 124
88 148
175 29
31 151
128 4
103 171
50 79
71 127
84 8
36 4
175 109...

output:

92546968269
200
1 70 137 78 161 40 147 179 109 33 56 104 175 111 86 29 14 72 153 177 168 197 83 87 73 38 146 113 67 126 65 159 199 66 13 46 16 122 18 62 51 181 80 74 171 125 98 103 188 55 85 195 20 160 6 30 134 116 35 64 7 68 99 172 102 118 71 127 136 101 52 120 157 22 176 167 91 144 48 193 82 156 1...

result:

ok correct!

Test #35:

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

input:

200 2
186 20
197 94
138 143
75 2
6 102
114 98
195 131
151 62
33 77
85 149
158 164
30 38
21 93
177 133
72 188
145 52
68 176
194 57
118 103
91 112
178 81
63 169
31 155
92 133
29 166
99 15
65 75
159 147
79 55
45 23
139 180
38 119
3 75
114 127
117 112
146 161
99 48
37 132
148 193
178 179
71 116
140 11
1...

output:

82875113284
152
1 75 103 35 118 3 64 33 183 113 150 184 46 96 19 191 182 5 157 49 37 175 132 115 84 57 161 53 86 146 119 136 16 105 141 142 38 12 151 40 62 47 30 11 102 160 6 140 27 55 167 50 120 79 83 131 67 22 90 195 130 23 68 101 176 185 61 158 116 154 71 124 156 171 152 129 56 174 92 169 177 32 ...

result:

ok correct!

Test #36:

score: 0
Accepted
time: 0ms
memory: 9900kb

input:

200 2
140 198
32 90
73 76
75 155
54 65
192 80
60 37
103 28
120 118
87 118
174 30
174 191
156 138
187 47
200 17
106 179
80 2
137 71
18 75
146 80
53 153
128 82
31 89
180 110
36 82
129 186
180 36
125 53
31 94
124 189
133 83
151 94
175 48
172 97
34 74
64 87
157 139
155 9
33 126
90 160
199 48
25 86
156 2...

output:

79408775618
143
1 140 129 136 91 143 186 130 76 62 158 132 145 92 164 53 189 154 194 124 125 68 16 86 23 46 25 141 40 89 94 152 127 151 31 65 190 134 184 147 197 54 38 139 74 70 84 34 66 166 60 83 183 111 88 133 52 174 165 77 56 176 10 55 99 168 114 169 13 135 96 90 200 182 8 17 14 167 48 126 3 50 3...

result:

ok correct!

Test #37:

score: 0
Accepted
time: 1ms
memory: 14016kb

input:

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

output:

31861270500
55
1 7 6 27 26 107 106 53 52 13 12 3 2 8 9 39 38 153 152 76 77 19 18 4 5 22 23 94 95 191 190 47 46 11 10 40 41 167 166 83 82 20 21 85 84 169 168 42 43 173 172 86 87 175 174

result:

ok correct!

Test #38:

score: 0
Accepted
time: 0ms
memory: 9964kb

input:

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

output:

26748477707
43
1 13 11 12 106 105 104 35 37 36 4 3 2 19 18 17 154 153 152 51 52 50 6 7 5 48 47 49 148 147 146 16 14 15 133 132 131 44 46 45 136 135 134

result:

ok correct!

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #39:

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

input:

2000 2
1653 466
455 1262
319 394
823 998
1135 313
244 809
563 850
1865 1303
609 1531
302 1084
504 163
1475 1799
534 258
1597 413
1161 330
676 1694
1315 1619
1646 32
1629 161
280 1765
102 877
474 503
1162 491
1182 1505
532 1820
525 1836
1682 808
1026 80
809 1334
1376 1783
401 708
1323 1443
1242 1215
...

output:

176031446963
333
1 459 239 1438 410 1805 937 605 1479 1216 1818 313 1325 198 242 126 423 1142 1101 438 838 1471 1133 512 467 872 1100 915 1912 783 375 1719 142 877 435 1892 334 325 632 457 658 1411 1284 1870 1003 1574 82 374 18 287 482 525 1452 660 338 1208 148 1046 326 1161 1726 97 652 1919 1766 15...

result:

ok correct!

Test #40:

score: 0
Accepted
time: 2ms
memory: 14012kb

input:

2000 2
892 750
281 1593
1698 1268
1500 653
348 1393
1617 797
1044 680
1517 1883
1081 1003
293 948
412 478
1733 690
1785 1377
1902 1304
1674 1565
1350 131
242 573
1778 275
296 1177
1090 1862
1503 1175
1620 207
1441 323
181 449
219 1911
671 1713
606 1360
1558 834
562 1576
1212 1077
257 1606
790 1496
1...

output:

202483759818
403
1 1506 186 25 1577 563 629 762 1452 1100 687 381 801 1190 1638 36 1952 560 1461 1098 108 668 1095 1726 787 1042 772 1569 915 1068 430 552 1572 1384 348 1157 1393 784 1197 1868 1680 650 553 1787 1462 691 1287 1437 1798 1775 897 808 999 524 1199 1729 1586 439 1196 1555 291 1171 1744 7...

result:

ok correct!

Test #41:

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

input:

2000 2
1581 867
670 1948
1286 1189
292 1357
1538 951
691 1646
502 1385
1071 812
482 469
1853 1303
614 774
363 62
506 91
718 951
1327 306
170 23
128 495
1841 263
178 588
271 252
930 1147
552 1150
1550 1584
685 1699
405 1353
1948 510
1632 327
1854 1167
1327 591
112 800
482 305
598 7
922 1645
1737 1811...

output:

184825610246
359
1 172 394 1959 1661 1191 1453 241 1449 1811 415 1773 934 13 1737 924 323 1152 1621 59 1304 670 936 324 1558 1810 598 510 1860 158 931 827 1630 1952 805 247 574 697 1491 1377 1484 336 1042 1609 1595 1891 647 254 1948 1032 1060 90 1041 86 1781 952 665 136 148 1782 982 1772 1206 1169 6...

result:

ok correct!

Test #42:

score: 0
Accepted
time: 4ms
memory: 12032kb

input:

2000 2
1217 1905
1210 453
765 261
1635 1637
1867 1564
1876 1141
1867 283
1093 1385
677 1050
284 1377
228 1393
541 1985
884 242
1714 1304
118 15
1992 1098
449 181
1549 246
84 1198
913 1522
666 1685
1704 263
589 1407
1870 906
1411 561
1252 562
282 17
1137 372
764 1171
1721 172
1990 1755
1231 1948
201 ...

output:

222905521782
416
1 1544 1036 1958 1787 549 1655 1080 1617 1414 1901 763 830 189 1694 982 1290 1647 561 470 1932 1012 695 1411 1371 620 593 602 434 1986 257 813 83 1085 1457 100 1733 1899 1322 1554 1011 1974 1994 14 818 970 1340 5 1403 1213 687 1305 1072 193 1171 1043 215 372 1422 683 141 1970 1511 1...

result:

ok correct!

Test #43:

score: 0
Accepted
time: 1ms
memory: 11988kb

input:

2000 2
989 1552
460 285
670 1653
190 1210
736 941
1555 647
648 363
1500 1908
241 1143
1702 1181
266 1622
409 955
1442 1033
1236 447
194 1312
463 1304
1994 397
835 564
22 982
1214 562
813 1812
1396 783
191 1449
1760 691
103 1289
493 439
333 1401
283 884
1419 832
1561 277
1582 294
1183 925
7 529
191 1...

output:

176264452857
344
1 146 1542 397 680 376 1823 469 1734 1688 309 527 1497 1994 1766 618 384 30 742 4 22 1684 604 982 943 1136 1595 940 1798 1302 959 776 144 554 143 1547 1758 733 685 1333 1723 339 1299 1086 682 353 1166 1783 1517 657 129 662 1241 1594 343 531 96 522 1597 1733 1487 1300 190 510 857 182...

result:

ok correct!

Test #44:

score: 0
Accepted
time: 0ms
memory: 9996kb

input:

2000 2
1900 687
259 1748
582 1542
1844 470
1752 1845
202 37
1206 807
646 269
1687 681
1482 1630
930 446
391 617
1424 1798
1481 1762
820 295
1263 1766
474 210
372 1407
117 1854
199 216
1779 789
937 555
1494 1909
1824 1319
1001 1938
144 45
785 196
1135 636
390 1866
1404 206
1790 524
1734 663
1604 1767...

output:

362696256044
704
1 1488 461 1747 1234 1736 1316 324 1677 1366 1981 819 1350 448 1561 831 1149 1933 1698 1974 527 796 951 218 1450 1069 1398 869 920 1723 361 826 455 911 1188 1273 1363 1787 519 207 1493 55 1826 1567 1419 629 1646 125 697 1639 85 506 241 1759 862 651 159 1514 372 1964 1407 1572 1466 7...

result:

ok correct!

Test #45:

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

input:

2000 2
284 498
512 963
418 534
206 1186
1506 1397
1511 459
992 742
1644 1013
1474 1397
1942 1941
1673 1229
1384 442
1397 1756
1876 280
2000 1932
1397 1993
1217 1474
1774 1204
737 1785
1356 1384
1473 1116
2000 1812
1617 1739
17 1979
229 1979
723 492
621 227
358 550
206 376
440 1675
1393 1790
909 341
...

output:

203246075730
402
1 423 1610 1778 1248 532 1886 988 1047 87 15 104 1192 1672 437 277 530 1811 362 686 1737 1331 1606 932 140 927 1470 1619 1055 810 477 1467 1239 1004 1608 1009 1771 1084 1255 454 378 812 1142 1648 1961 847 1488 468 701 1638 1067 1876 183 890 983 1191 1994 696 1700 1950 1064 334 1242 ...

result:

ok correct!

Test #46:

score: 0
Accepted
time: 1ms
memory: 14108kb

input:

2000 2
1237 1826
571 1212
1932 1106
88 1218
764 916
1880 854
700 1803
585 679
891 1587
712 1921
233 738
668 1927
1167 918
432 1789
1377 1585
1344 916
692 1546
1749 1947
1571 1869
1484 1846
1531 1997
694 1957
758 567
1649 181
3 1062
987 1320
533 1487
1402 1085
936 1807
1526 752
183 1513
403 187
1796 ...

output:

404938855945
815
1 1556 348 1319 279 523 727 634 755 1272 175 1938 886 1429 1315 952 1840 1914 1416 1716 1544 287 938 1967 399 1799 370 178 1304 1375 210 364 392 535 1522 1343 1002 339 383 152 1637 796 812 200 613 1311 1793 198 121 1626 442 1043 734 1122 1468 1276 694 1930 1233 723 1480 433 552 1467...

result:

ok correct!

Test #47:

score: 0
Accepted
time: 14ms
memory: 12028kb

input:

2000 2
593 1134
610 1128
274 1314
1799 123
1738 1823
523 1117
1272 529
1439 225
1275 450
286 1117
34 365
935 1460
1200 1008
475 1622
854 819
1632 890
996 1743
237 1665
1669 1985
1767 1934
1799 783
12 1601
342 1623
924 144
1269 146
1799 340
1280 1669
1270 1128
950 1245
1686 1730
1117 1202
178 393
180...

output:

273811282141
553
1 1344 766 1744 1791 1169 1720 403 1386 1219 627 1288 1524 1296 1910 237 1743 407 1337 592 967 1969 674 493 181 1000 582 199 438 52 1748 1559 1051 1162 903 577 812 129 1617 1793 435 1348 1126 602 573 334 1380 795 1018 641 226 1332 1685 1142 912 729 70 317 968 1501 1976 225 1154 1998...

result:

ok correct!

Test #48:

score: -3
Time Limit Exceeded

input:

2000 2
1383 1
1 1410
1 1106
1154 1
1 1202
1794 1
1512 1
1744 1
221 1
1 917
1637 1
1 118
1 423
164 1
1 1881
479 1
1 1029
1 567
1 193
1 1364
1 45
1458 1
692 1
1765 1
807 1
897 1
43 1
1243 1
1 681
1272 1
1 579
122 1
1 1241
1299 1
1558 1
1 88
726 1
1 654
1900 1
1895 1
1 384
1 661
223 1
1 956
1 1112
38 1...

output:

result:

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Dangerous Syscalls

Test #83:

score: 0
Dangerous Syscalls

input:

2000 3
1359 90
1703 163
158 188
360 1501
195 664
1414 215
1546 1756
536 1096
1726 1223
1150 104
1757 703
1982 282
1023 998
1180 419
576 1759
1496 1993
44 670
1703 952
855 849
1998 1399
1280 980
1533 1090
1270 678
1680 387
469 1734
1799 263
473 588
303 226
5 295
1489 1471
1094 1667
1912 210
1368 1360...

output:

result:

Subtask #6:

score: 0
Skipped

Dependency #5:

0%
English 繁體中文 简体中文

Server Time: 2024-12-05 23:34:06 | OpenSource Project