QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242905 | #6654. 大纲 | phtniit | WA | 12ms | 36700kb | C++14 | 1.9kb | 2023-11-07 18:20:21 | 2023-11-07 18:20:21 |
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;
}
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: 36700kb
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: -100
Wrong Answer
time: 11ms
memory: 36332kb
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:
Reasonable Reasonable
result:
wrong answer 1st lines differ - expected: 'Unreasonable', found: 'Reasonable'