QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282992#6654. 大纲one_god_and_two_dogs#TL 54ms18744kbC++141.4kb2023-12-13 17:11:352023-12-13 17:11:36

Judging History

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

  • [2023-12-13 17:11:36]
  • 评测
  • 测评结果:TL
  • 用时:54ms
  • 内存:18744kb
  • [2023-12-13 17:11:35]
  • 提交

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);
        memset(L,-1,sizeof L);
        memset(R,-1,sizeof R);
        for(int i=1; i<=n; ++i)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: 27ms
memory: 12180kb

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: 46ms
memory: 12076kb

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: 18744kb

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
Time Limit Exceeded

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: