QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#275160 | #6654. 大纲 | rageOfThunder# | AC ✓ | 23ms | 14120kb | C++14 | 2.3kb | 2023-12-04 14:19:49 | 2023-12-04 14:19:49 |
Judging History
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