QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#769863 | #6654. 大纲 | ANIG# | WA | 30ms | 7452kb | C++14 | 1.3kb | 2024-11-21 19:39:51 | 2024-11-21 19:39:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
vector<vector<int>> ver;
int n,Flag;
const int inf=1e9+1e6;
pair<int,int> dfs(int u){
int l=0,r=0;
if(!ver[u].size()){
if(a[u]!=-1) l=r=a[u];
return make_pair(0,inf);
}
int cnt=0;
vector<pair<int,int>> tmp;
for(auto p:ver[u]){
auto T=dfs(p);
if(Flag||T.first>T.second){
Flag=1;
return make_pair(inf,0);
}
tmp.emplace_back(T);
l=max(l,T.first);
r=max(r,T.second);
}
if(l>r) return make_pair(l,r);
for(auto pt:tmp){
if(pt.first==l) cnt++;
}
if(cnt>1) l++;
cnt=0;
for(auto pt:tmp){
if(pt.second==r) cnt++;
}
if(cnt>1) r++;
if(a[u]==-1) return make_pair(l,r);
if(l<=a[u]&&a[u]<=r) return make_pair(a[u],a[u]);
return make_pair(inf,0);
}
void solve(){
cin>>n;
a=vector<int>(n+1);
for(int i=1; i<=n; i++){
cin>>a[i];
}
ver=vector<vector<int>>(n+1);
for(int i=1; i<n; i++){
int x,y;
cin>>x>>y;
ver[x].emplace_back(y);
}
Flag=0;
auto T=dfs(1);
if(Flag==0&&T.first<=T.second) cout<<"Reasonable\n";
else cout<<"Unreasonable\n";
}
int main(){
cin.tie(0),cout.tie(0)->sync_with_stdio(false);
int T;
cin>>T;
while(T--) solve();
return 0;
}
/*
2
3
0 -1 0
1 2
2 3
3
0 -1 0
1 2
1 3
*/
详细
Test #1:
score: 100
Accepted
time: 30ms
memory: 7452kb
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: 29ms
memory: 7396kb
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'