QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308207#6654. 大纲ckiseki#WA 28ms6868kbC++202.1kb2024-01-19 18:38:592024-01-19 18:39:00

Judging History

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

  • [2024-01-19 18:39:00]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:6868kb
  • [2024-01-19 18:38:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef local
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int T;
  cin >> T;
  while (T--) {

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];

    auto g = vector(n, vector<int>());
    for (int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      g[u].emplace_back(v);
    }

    bool ok = true;
    vector<int> l(n), r(n);
    const auto dfs = [&](auto self, int i) -> void {
      if (g[i].empty()) {
        l[i] = 0, r[i] = 2e9; return;
      }

      for (int j : g[i]) {
        self(self, j);
      }

      {
        int mx = 0;
        for (int j : g[i]) {
          mx = max(mx, l[j]);
        }
        int cnt = 0;
        for (int j : g[i]) {
          if (l[j] == mx)
            ++cnt;
        }
        if (cnt > 1) ++mx;
        l[i] = mx;
      }
      {
        int mx = 0;
        for (int j : g[i]) {
          mx = max(mx, r[j]);
        }
        int cnt = 0;
        for (int j : g[i]) {
          if (r[j] == mx)
            ++cnt;
        }
        if (cnt > 1) ++mx;
        r[i] = mx;
      }

      if (a[i] != -1) {
        if (a[i] < l[i] || a[i] > r[i])
          ok = false;
        l[i] = r[i] = a[i];
      }

    };

    dfs(dfs, 0);

    cout << (ok ? "Reasonable\n" : "Unreasonable\n");
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 20ms
memory: 6868kb

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: 28ms
memory: 6824kb

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'