QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242910 | #6654. 大纲 | phtniit | WA | 28ms | 41040kb | C++14 | 1.9kb | 2023-11-07 18:22:44 | 2023-11-07 18:22:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int, int> pii;
// std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// priority_queue<int, vector<int>, greater<int>> minq;
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// fflush(stdout);
const int inf = 1000000007;
const i64 prm = 998244353;
const i64 inf2 = ((i64)inf) * inf;
const int maxn = 1100010; // 1.1e6
inline int read(){
int x=0,f=0; char ch=getchar();
while(!isdigit(ch)) f|=(ch==45),ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
const int lim = inf + maxn;
int a[maxn], b[maxn];
int w[maxn];
vector<int> g[maxn];
bool dfs(int u) {
if (g[u].size() > 0) { // not leaf
for (auto v: g[u]) {
if (not dfs(v)) {
return false;
}
}
int mx = 0, cnt1 = 0;
for (auto v: g[u]) {
if (mx == b[v]) {
cnt1++;
}
if (mx < b[v]) {
mx = b[v];
cnt1 = 1;
}
}
b[u] = mx + (cnt1 > 1);
int mn = 0, cnt2 = 0;
for (auto v: g[u]) {
if (mn == a[v]) {
cnt2++;
}
if (mn < a[v]) {
mn = a[v];
cnt2 = 1;
}
}
a[u] = mn + (cnt1 > 1);
} else {
a[u] = 0;
b[u] = lim;
}
if (w[u] != -1) {
if (w[u] < a[u]) return false;
if (w[u] > b[u]) return false;
a[u] = b[u] = w[u];
}
return true;
}
void once() {
int n = read();
for (int i = 1; i <= n; ++i) {
w[i] = read();
g[i].clear();
}
for (int i = 1; i < n; ++i) {
int u = read(), v = read();
g[u].push_back(v);
}
if (not dfs(1)) {
puts("Unreasonable");
} else {
puts("Reasonable");
}
}
int main() {
int tes = 1;
tes = read();
while (tes--) {
once();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 36844kb
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: 15ms
memory: 36780kb
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: 28ms
memory: 41040kb
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: 17ms
memory: 34216kb
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: 13ms
memory: 34312kb
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: -100
Wrong Answer
time: 12ms
memory: 34356kb
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:
wrong answer 29th lines differ - expected: 'Reasonable', found: 'Unreasonable'