QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #282993 | #6654. 大纲 | one_god_and_two_dogs# | WA | 54ms | 18792kb | C++14 | 1.4kb | 2023-12-13 17:12:51 | 2023-12-13 17:12:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
int T;
int a[M];
vector<int>Q[M];
int L[M],R[M];
bool f;
void dfs(int now,int Fa) {
if(!f)return;
if(Q[now].size()==1&&Q[now][0]==Fa) {
if(~a[now])L[now]=R[now]=a[now];
else L[now]=0;
return;
}
int mxl=-1,mxr=-1,cntl=0,cntr=0;
bool Have=false;
for(int i=0; i<Q[now].size(); ++i) {
int To=Q[now][i];
if(To==Fa)continue;
dfs(To,now);
if(L[To]>mxl)mxl=L[To],cntl=0;
else if(L[To]==mxl)cntl++;
if(R[To]>mxr)mxr=R[To],cntr=0;
else if(R[To]==mxr)cntr++;
if(R[To]==-1)Have=true;
}
if(cntl>0)mxl++;
if(cntr>0)mxr++;
if(Have||R[now]==-1)mxr=-1;
if(a[now]!=-1) {
if(mxl<=a[now]&&(a[now]<=mxr||mxr==-1))L[now]=R[now]=a[now];
else f=false;
}else L[now]=mxl,R[now]=mxr;
}
int main() {
scanf("%d",&T);
while(T--) {
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i)L[i]=R[i]=-1,Q[i].clear();
for(int i=1; i<=n; ++i)scanf("%d",&a[i]);
for(int i=1; i<n; ++i) {
int u,v;
scanf("%d%d",&u,&v);
Q[u].push_back(v);
Q[v].push_back(u);
}
f=true;
dfs(1,0);
if(f)puts("Reasonable");
else puts("Unreasonable");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 26ms
memory: 11696kb
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: 32ms
memory: 11348kb
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: 54ms
memory: 18792kb
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: -100
Wrong Answer
time: 30ms
memory: 8432kb
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 Reasonable Reasonable Unreasonable Reasonable Reasonable Unreasonable Reasonable Reasonable Reasonable Reasonable Reasonable Reasonable Reasonable Reasonable Reasonable Reason...
result:
wrong answer 12th lines differ - expected: 'Unreasonable', found: 'Reasonable'