QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#242910#6654. 大纲phtniitWA 28ms41040kbC++141.9kb2023-11-07 18:22:442023-11-07 18:22:45

Judging History

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

  • [2023-11-07 18:22:45]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:41040kb
  • [2023-11-07 18:22:44]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'