QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#876461#370. Cityduongnc0008 124ms8268kbC++201.2kb2025-01-30 21:30:412025-01-30 21:30:43

Judging History

This is the latest submission verdict.

  • [2025-01-30 21:30:43]
  • Judged
  • Verdict: 8
  • Time: 124ms
  • Memory: 8268kb
Show
  • [2025-01-30 21:30:41]
  • Submitted

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

void Encode(int N, int A[], int B[]) {
	vector<vector<int>> g(N);
	for (int i = 0; i < N - 1; ++i) {
		int u = A[i], v = B[i];
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	int tdfs = 0;
	vector<i64> tin(N), tout(N);
	auto dfs = [&](auto self, int u, int p) -> void {
		tin[u] = tdfs++;
		for (auto v : g[u]) if (v != p) {
			self(self, v, u);
		}
		tout[u] = tdfs;
		assert(tout[u] < 1 << 18);
	};
	dfs(dfs, 0, -1);
	for (int i = 0; i < N; ++i) Code(i, tin[i] * (1ll << 18) + tout[i]);
}
Source code, Language: C++20

Device

#include "Device.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

void InitDevice() {
}

const int lim = (1 << 18) - 1;

int Answer(i64 S, i64 T) {
	int Sl = S >> 18, Sr = S & lim;
	int Tl = T >> 18, Tr = T & lim;
	if (Tl <= Sl and Sr <= Tr) return 0;
	if (Sl <= Tl and Tr <= Sr) return 1;
	return 2;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 0ms
memory: 5968kb

input:

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

output:

10 1310726 786438 2097161 1835017 262147 1572874 524291 1048581 2359306

input:

Interaction has been finished!

output:

0
1
0
1
1
0
0
1
1
2
2
0
2
2
2
2
2
0
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
2
2
2
0
2
2
2359306

result:

ok

Test #2:

score: 8
Accepted
time: 2ms
memory: 5968kb

input:

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

output:

10 1835016 786436 1310726 2359306 2097162 524293 262150 1572872 1048581

input:

Interaction has been finished!

output:

0
1
0
1
0
1
1
0
1
2
2
1
0
2
1
2
1
2
2
2
2
2
0
2
2
2
0
2
2
2
2
2
2
2
2
2
0
2
0
2
2
2
2
2
2
2359306

result:

ok

Test #3:

score: 8
Accepted
time: 0ms
memory: 6092kb

input:

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

output:

10 1835016 1572871 1048585 2097161 2359306 1310729 786442 524291 262147

input:

Interaction has been finished!

output:

0
0
0
1
0
0
0
1
1
2
1
1
1
0
2
0
1
2
2
2
2
0
2
2
1
0
0
2
0
2
0
1
2
0
2
2
2
2
2
2
2
2
2
2
2
2359306

result:

ok

Test #4:

score: 8
Accepted
time: 0ms
memory: 5968kb

input:

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

output:

10 786436 1835016 262148 1310726 1572872 2359306 1048586 524291 2097162

input:

Interaction has been finished!

output:

0
0
1
0
0
0
1
1
0
2
0
1
2
2
1
0
1
2
2
0
0
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
2359306

result:

ok

Test #5:

score: 8
Accepted
time: 0ms
memory: 5972kb

input:

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

output:

10 2097161 1310726 2359306 1572871 1048583 786436 262151 524292 1835018

input:

Interaction has been finished!

output:

0
1
1
1
0
1
0
0
1
2
1
0
2
2
0
1
0
2
2
0
0
2
2
2
2
2
2
0
1
2
2
2
2
2
0
2
2
2
2
2
2
2
2
2
2
2359306

result:

ok

Test #6:

score: 8
Accepted
time: 0ms
memory: 3840kb

input:

9 36
3 6
4 3
6 8
4 2
3 1
0 7
0 4
7 5
7 0
5 0
0 4
0 3
2 0
1 0
6 0
0 8
7 5
4 7
3 7
2 7
1 7
6 7
8 7
5 4
5 3
5 2
5 1
6 5
8 5
3 4
4 2
4 1
4 6
8 4
2 3
3 1
6 3
8 3
1 2
2 6
2 8
1 6
8 1
6 8

output:

9 1835016 2097161 1048584 786441 524291 1310727 262147 1572871

input:

Interaction has been finished!

output:

0
0
1
1
0
0
0
1
1
2
2
2
2
2
2
2
2
2
2
2
2
0
1
1
1
0
2
1
0
0
2
2
2
2
2
1
2097161

result:

points 1.0

Test #7:

score: 8
Accepted
time: 0ms
memory: 5972kb

input:

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

output:

10 1310728 1048581 2359306 524293 262146 1572871 786436 1835016 2097162

input:

Interaction has been finished!

output:

1
0
0
1
1
1
0
0
0
2
2
0
1
2
2
2
2
0
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
2
2
2
2
2359306

result:

ok

Test #8:

score: 8
Accepted
time: 0ms
memory: 3968kb

input:

5 10
4 1
0 4
0 2
2 3
0 4
2 0
1 0
3 0
2 4
4 1
4 3
1 2
2 3
1 3

output:

5 524291 786437 1048581 262147

input:

Interaction has been finished!

output:

1
0
0
0
2
1
2
2
1
2
1048581

result:

points 1.0

Test #9:

score: 8
Accepted
time: 2ms
memory: 3840kb

input:

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

output:

7 786436 1048583 1572871 524292 1310727 262146

input:

Interaction has been finished!

output:

1
0
1
1
1
0
1
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1572871

result:

points 1.0

Test #10:

score: 8
Accepted
time: 0ms
memory: 3968kb

input:

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

output:

8 1048581 786438 262146 1310726 1572871 1835016 524295

input:

Interaction has been finished!

output:

1
1
1
1
0
1
1
2
2
2
2
2
2
2
2
2
2
2
1
1
0
0
2
1
0
2
2
2
1835016

result:

points 1.0

Test #11:

score: 8
Accepted
time: 0ms
memory: 3840kb

input:

6 15
0 3
1 4
1 5
4 2
0 1
1 0
0 5
4 0
0 3
0 2
1 5
4 1
1 3
2 1
5 4
3 5
5 2
3 4
2 4
3 2

output:

6 524294 1048581 262146 786437 1310726

input:

Interaction has been finished!

output:

0
1
0
1
1
1
0
2
0
2
2
2
2
0
2
1310726

result:

points 1.0

Test #12:

score: 8
Accepted
time: 2ms
memory: 3840kb

input:

4 6
0 2
2 3
0 1
0 1
0 2
0 3
2 1
3 1
3 2

output:

4 786436 262147 524291

input:

Interaction has been finished!

output:

1
1
1
2
2
0
786436

result:

points 1.0

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 92
Accepted
time: 60ms
memory: 6996kb

input:

700 244650
407 643
680 336
573 208
466 455
159 648
575 549
50 567
251 211
211 481
530 513
136 334
112 492
175 396
643 483
265 132
20 160
174 550
251 90
99 236
579 374
670 613
495 379
251 170
652 61
495 467
27 317
202 484
420 592
542 354
565 650
35 88
216 681
277 219
299 171
220 647
418 433
434 660
2...

output:

700 123994587 147063346 50331841 168559237 94110058 175112862 129761776 115343801 181404341 154403408 124781021 70779151 8126497 169607816 148636217 89915736 164627062 164889206 42205346 113246644 75497783 64225526 95158636 112460206 102236551 33292416 5767193 2097161 179307181 43778217 153616971 16...

input:

Interaction has been finished!

output:

0
0
0
0
1
0
1
1
1
1
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
1
0
1
1
1
0
1
1
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
1
1
1
1
1
0
1
0
0
0
1
0
0
0
0
1
...

result:

points 1.0

Test #14:

score: 92
Accepted
time: 60ms
memory: 6224kb

input:

699 243951
59 192
191 301
270 524
135 496
647 573
174 262
662 43
371 50
655 434
123 242
209 46
612 646
11 533
156 443
322 462
329 558
417 383
283 263
615 504
29 520
391 135
546 535
54 264
382 651
541 427
536 456
295 169
645 303
494 21
282 179
329 490
191 67
697 55
226 276
32 160
226 482
392 56
144 1...

output:

699 101450116 149422652 93323621 74711326 40108187 67895556 89653593 91750753 81002807 136053259 262818 19136586 20185168 105906581 114295223 135004676 132907516 152568391 18874442 120848858 25428066 145490476 9175077 51380422 15466556 11010094 107479454 146539056 13107254 38011026 129499636 5269115...

input:

Interaction has been finished!

output:

1
0
1
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
1
1
0
0
0
1
0
1
1
0
1
1
1
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
1
1
1
0
0
1
1
0
0
1
0
0
...

result:

points 1.0

Test #15:

score: 92
Accepted
time: 58ms
memory: 4736kb

input:

700 244650
32 619
369 483
58 148
484 103
190 630
589 659
90 204
515 464
215 254
688 658
454 3
286 582
158 246
90 164
648 13
602 240
237 8
36 620
31 558
515 560
302 39
373 418
288 388
50 516
26 514
190 467
190 439
600 35
258 421
148 214
251 111
50 62
10 530
624 466
666 637
666 692
285 650
137 686
280...

output:

700 51380421 126616036 116392381 26214531 169607822 152044101 83362111 12845107 33816707 54001893 9437227 165937786 121373136 54526162 66060541 53739726 84672836 60555504 11272248 34865286 73662747 140771867 95682926 175112861 61604076 40632477 138674706 8388641 44040362 123732441 94634364 97780087 ...

input:

Interaction has been finished!

output:

1
1
0
1
1
1
0
0
0
0
1
1
0
0
1
1
1
1
0
1
1
1
1
1
0
1
0
1
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
...

result:

points 1.0

Test #16:

score: 92
Accepted
time: 60ms
memory: 6480kb

input:

700 244650
230 624
291 145
565 474
12 535
152 335
438 692
136 13
199 155
255 47
546 152
293 254
427 131
71 388
31 231
124 522
503 23
320 545
322 480
674 535
247 415
301 163
226 63
560 367
361 103
391 149
483 661
262 632
337 79
45 59
182 489
526 425
275 369
256 598
42 487
125 63
661 23
181 152
366 29...

output:

700 81789241 179307181 175899302 82051386 141558301 61079786 52166856 28573808 1310756 88342866 107479457 167772807 7602212 131072503 67633473 109314493 42991795 28311667 47186107 140247582 160694886 177996458 34603171 151519813 156238423 101450130 148898361 90702171 114557366 17039426 102236551 175...

input:

Interaction has been finished!

output:

1
0
1
1
0
1
1
0
1
0
0
1
0
1
1
1
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
0
0
0
1
1
1
1
1
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
0
1
1
1
0
1
0
0
1
0
1
0
1
...

result:

points 1.0

Test #17:

score: 0
Wrong Answer
time: 124ms
memory: 8268kb

input:

250000 250000
98377 99261
85304 211210
196850 193036
80796 130416
3160 72100
145991 142897
200915 46448
218676 213491
89680 96159
73896 8598
61659 226081
22401 122629
228272 20662
17177 215756
118511 136128
95692 43162
78229 30135
134970 150179
163578 188576
213241 99059
203107 94390
139934 51361
18...

output:

250000 -1031606109 598460652 -339625231 599705840 -1126895818 -1077399565 -1247859352 -1775835765 -323028176 998067936 777997208 1164136794 -1258083007 -1892097073 663276003 913427871 1253839536 -214467377 764136293 1730894284 -81232180 -299861111 1078251538 -2116902794 985763505 -1624463409 3037605...

input:

Interaction has been finished!

output:

2
1
2
1
2
0
0
0
2
1
2
2
2
0
1
0
1
0
0
0
1
0
2
0
2
0
0
1
1
2
1
2
0
2
2
1
2
0
0
1
1
2
0
1
1
0
0
0
2
1
0
1
0
2
2
1
2
1
0
2
2
1
2
2
2
0
2
1
1
1
2
2
0
0
2
2
1
2
2
2
2
2
0
2
1
1
2
0
1
2
1
0
0
0
0
0
0
1
2
2
2
1
1
1
2
0
0
2
0
1
0
2
1
1
2
2
2
1
2
0
1
0
0
0
0
2
0
1
2
0
1
1
2
2
0
1
0
1
1
0
1
2
0
0
2
2
1
1
1
1
...

result:

wrong answer Wrong Answer [6] (Query #2 returned 1 but expected 2)
English 繁體中文 简体中文

Server Time: 2025-02-06 22:55:21 | OpenSource Project