QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#275160#6654. 大纲rageOfThunder#AC ✓23ms14120kbC++142.3kb2023-12-04 14:19:492023-12-04 14:19:49

Judging History

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

  • [2023-12-04 14:19:49]
  • 评测
  • 测评结果:AC
  • 用时:23ms
  • 内存:14120kb
  • [2023-12-04 14:19:49]
  • 提交

answer

// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T &x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T &x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 1e5 + 10;
int n, a[N], l[N], r[N];
bool flag;
vector <int> v[N];
void dfs(int x) {
	if (a[x] != -1) {
		if (v[x].empty()) {
			l[x] = r[x] = a[x];
			return;
		}
		int s1 = 0, s2 = 0, s3 = 0;
		// 只能ai-1 只能 ai 都能
		for (int i: v[x]) {
			dfs(i);
			// chkmax(l[i], a[x] - 1);
			chkmin(r[i], a[x]);
			if (l[i] > r[i]) flag = false;//, debug << "~ " << x << " " << i << endl;
			if (r[i] < a[x] - 1) continue;
			if (l[i] == r[i]) {
				if (r[i] == a[x]) s2++;
				else s1++;
			} else {
				if (r[i] == a[x]) s3++;
				else s1++;
			}
			// if (l[i] < r[i]) s3++;
			// else if (r[i] == a[x]) s2++;
			// 	else s1++;
		}
		l[x] = r[x] = a[x];
		bool g = false;
		//恰好一个ax
		if (s2 == 1 || (s2 == 0 && s3)) g = true;
		//全是ax-1
		if (!s2 && s1 + s3 > 1) g = true;
		if (!g) flag = false;
	} else {
		if (v[x].empty()) {
			l[x] = 0, r[x] = 1e9;
			return;
		}
		int L = 0, cntl = 0;
		int R = 0, cntr = 0;
		for (int i: v[x]) {
			dfs(i);
			if (l[i] > L) {
				L = l[i], cntl = 1;
			} else if (l[i] == L) cntl++;
			if (r[i] > R) {
				R = r[i], cntr = 1;
			} else if (r[i] == R) cntr++;
		}
		l[x] = L + (cntl > 1);
		r[x] = R + (cntr > 1);
	}
	// debug << x << " " << l[x] << " " << r[x] << " " << flag << endl;
}
void zhk() {
	flag = true;
	read(n);
	F(i, 1, n) v[i].clear(), read(a[i]);
	F(i, 1, n - 1) {
		int x, y; read(x), read(y);
		v[x].push_back(y);
	}
	dfs(1);
	puts(flag ? "Reasonable" : "Unreasonable");
}
signed main() {
	int _ = 1;
	cin >> _;
	while (_--) zhk();
	return 0;
}
/* why?
*/

详细

Test #1:

score: 100
Accepted
time: 16ms
memory: 8224kb

input:

2
65535
-1 1000000000 -1 1000000000 1000000000 1000000000 -1 -1 -1 -1 -1 -1 1000000000 1000000000 1000000000 1000000000 -1 1000000000 1000000000 -1 1000000000 -1 1000000000 1000000000 -1 -1 -1 -1 -1 -1 -1 -1 -1 1000000000 1000000000 -1 1000000000 -1 -1 -1 1000000000 1000000000 1000000000 1000000000 ...

output:

Reasonable
Unreasonable

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 11ms
memory: 8320kb

input:

2
65535
1000000000 -1 -1 -1 1000000000 -1 -1 -1 -1 -1 1000000000 1000000000 -1 1000000000 -1 -1 -1 -1 1000000000 -1 1000000000 1000000000 -1 1000000000 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 1000000000 -1 -1 1000000000 -1 -1 1000000000 1000000000 1000000000 -1 -1 -1 -1 1000000000 10000...

output:

Unreasonable
Reasonable

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 23ms
memory: 14120kb

input:

2
99999
49999 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...

output:

Reasonable
Reasonable

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 7ms
memory: 6472kb

input:

100000
2
503237730 503237730
1 2
2
940454426 940454426
1 2
2
248079005 -1
1 2
2
74614856 74614857
1 2
2
64379558 64379558
1 2
2
306909809 -1
1 2
2
-1 966615641
1 2
2
698391106 698391107
1 2
2
223750421 -1
1 2
2
705201637 705201637
1 2
2
256204065 -1
1 2
2
723177111 168932444
1 2
2
228089673 22808967...

output:

Reasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Reasonable
Reasonable
Un...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 11ms
memory: 6536kb

input:

66666
3
530204916 -1 -1
2 3
1 2
3
476528072 476528072 476528072
1 2
2 3
3
-1 841888306 841888306
1 3
1 2
3
319191766 319191766 -1
3 2
1 3
3
177048577 531221023 -1
1 2
1 3
3
598759147 991100533 416954424
1 3
3 2
3
210423414 263192668 -1
1 2
1 3
3
902429034 -1 961317874
1 3
1 2
3
662280681 -1 33815376...

output:

Reasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable...

result:

ok 66666 lines

Test #6:

score: 0
Accepted
time: 7ms
memory: 5992kb

input:

50000
3
-1 6 6
1 3
1 2
5
0 -1 -1 0 -1
4 5
4 2
2 3
1 4
3
859025665 859025665 859025665
1 2
2 3
4
1 1 1 1
3 2
2 4
1 3
3
2 -1 -1
3 2
1 3
4
2 1 1 2
4 2
1 4
4 3
2
2 2
1 2
3
-1 1 2
1 3
3 2
3
1 1 1
1 3
3 2
2
-1 8
1 2
4
4 4 296285101 1
2 3
1 2
1 4
4
-1 -1 -1 0
2 4
1 2
2 3
5
-1 0 0 0 0
1 4
1 2
1 5
1 3
4
-1 6...

output:

Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonabl...

result:

ok 50000 lines

Test #7:

score: 0
Accepted
time: 12ms
memory: 6496kb

input:

20000
9
2 1 1 2 0 2 2 2 0
9 5
6 9
6 2
4 7
1 4
8 6
6 3
7 8
5
14672963 -1 14672966 -1 -1
5 3
2 5
4 2
1 4
18
3 2 0 3 0 0 0 2 1 -1 2 2 1 0 0 0 2 0
4 13
4 14
4 16
4 11
4 12
4 10
4 17
8 18
4 9
14 5
4 7
8 2
1 8
18 3
1 4
4 15
4 6
12
-1 3 -1 -1 -1 1 -1 -1 -1 0 -1 0
8 9
12 5
10 7
4 2
4 12
2 10
3 4
2 11
1 3
2 ...

output:

Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Rea...

result:

ok 20000 lines

Test #8:

score: 0
Accepted
time: 12ms
memory: 6248kb

input:

5000
54
-1 -1 0 -1 -1 0 -1 3 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 1 -1 -1 -1 0 0 0 -1 0 -1 0 -1 -1 -1 -1 -1 -1
12 53
45 15
38 5
22 17
16 38
50 3
53 34
32 47
36 50
35 36
13 32
25 10
24 16
3 48
6 39
42 7
41 23
15 20
8 14
49 28
26 11
34 18
28 8
17 24
47 40
...

output:

Reasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable...

result:

ok 5000 lines

Test #9:

score: 0
Accepted
time: 9ms
memory: 7104kb

input:

2000
93
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
22 21
27 51
73 ...

output:

Reasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Unr...

result:

ok 2000 lines

Test #10:

score: 0
Accepted
time: 13ms
memory: 6416kb

input:

500
185
7 1 1 -1 1 -1 -1 -1 1 0 -1 1 0 1 1 -1 1 1 0 0 2 2 1 2 2 1 1 1 1 0 -1 7 -1 0 -1 -1 1 1 1 -1 -1 0 -1 0 -1 2 -1 0 0 1 1 -1 0 2 -1 -1 1 2 1 1 0 2 0 -1 -1 1 2 4 -1 4 0 -1 0 1 3 2 -1 -1 0 -1 3 2 0 2 2 0 0 0 0 2 -1 -1 -1 0 -1 2 1 -1 1 -1 7 0 1 -1 1 -1 0 1 0 1 5 1 2 1 1 -1 2 0 2 2 -1 0 -1 1 1 2 1 1 ...

output:

Unreasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Reas...

result:

ok 500 lines

Test #11:

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

input:

200
1068
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...

output:

Reasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Re...

result:

ok 200 lines

Test #12:

score: 0
Accepted
time: 15ms
memory: 6800kb

input:

50
6555
10 -1 2 1 1 -1 2 2 2 2 2 -1 2 1 1 0 1 2 2 0 0 0 2 1 3 0 0 0 -1 1 1 1 -1 0 1 1 1 0 2 -1 2 -1 1 2 1 1 -1 2 2 0 2 2 -1 1 2 -1 2 0 2 -1 1 0 3 1 0 1 0 1 0 -1 2 0 2 1 -1 1 0 1 0 2 1 1 2 1 1 2 2 2 1 -1 -1 -1 2 1 4 0 -1 -1 1 1 -1 -1 1 -1 1 0 2 0 1 2 0 2 2 0 -1 -1 2 0 -1 2 0 -1 0 0 4 2 2 2 1 1 1 1 -1...

output:

Reasonable
Reasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Reasonable
Unreasonable
Reasonab...

result:

ok 50 lines

Test #13:

score: 0
Accepted
time: 9ms
memory: 8316kb

input:

20
14327
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...

output:

Reasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Unreasonable
Unreasonable
Unreasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Reasonable
Reasonable

result:

ok 20 lines

Test #14:

score: 0
Accepted
time: 20ms
memory: 7796kb

input:

8
35399
-1 -1 4 1 4 2 -1 4 -1 2 1 1 -1 2 3 -1 3 4 -1 -1 6 0 0 3 -1 5 -1 5 3 0 -1 -1 -1 -1 0 -1 1 5 3 4 4 2 1 6 2 2 -1 4 -1 0 -1 -1 4 1 0 0 5 -1 0 -1 2 2 2 1 1 6 2 2 2 3 -1 3 4 4 -1 -1 2 -1 3 0 0 2 -1 -1 3 -1 3 1 2 2 -1 6 4 0 -1 -1 -1 -1 3 -1 -1 1 -1 1 4 3 4 2 -1 6 3 -1 2 -1 2 3 -1 0 -1 -1 1 6 2 6 -1...

output:

Unreasonable
Unreasonable
Reasonable
Reasonable
Unreasonable
Unreasonable
Reasonable
Reasonable

result:

ok 8 lines

Test #15:

score: 0
Accepted
time: 15ms
memory: 9592kb

input:

4
28617
-1 -1 15040626 -1 -1 68730989 68730991 -1 68730984 8635907 68730988 -1 -1 -1 -1 68730983 68730993 68730992 -1 -1 68730989 29772797 68730985 34273767 -1 61879811 68730988 67015657 68730993 25288248 68730987 -1 -1 -1 19396694 68730986 -1 7501231 68730991 68730986 -1 68730988 30125487 63758400 ...

output:

Unreasonable
Reasonable
Unreasonable
Unreasonable

result:

ok 4 lines

Test #16:

score: 0
Accepted
time: 22ms
memory: 9792kb

input:

2
100000
9 -1 -1 1 2 2 1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 2 0 -1 1 -1 2 -1 0 -1 -1 -1 0 0 1 -1 -1 -1 -1 -1 2 -1 0 0 -1 0 -1 2 -1 -1 -1 -1 -1 -1 -1 0 -1 1 -1 0 -1 1 -1 0 1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 2 -1 1 -1 2 -1 0 1 0 -1 -1 1 -1 -1 -1 1 2 -1 -1 -1 -1 -1 2 -1 -1 -1 1 -1 -1 1 -1 1 0 -1...

output:

Reasonable
Unreasonable

result:

ok 2 lines