QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242905#6654. 大纲phtniitWA 12ms36700kbC++141.9kb2023-11-07 18:20:212023-11-07 18:20:21

Judging History

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

  • [2023-11-07 18:20:21]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:36700kb
  • [2023-11-07 18:20:21]
  • 提交

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'