QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#769838 | #6652. 着色 | ANIG# | RE | 0ms | 0kb | C++14 | 1.2kb | 2024-11-21 19:34:24 | 2024-11-21 19:34:24 |
answer
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
vector<vector<int>> ver;
int n;
const int inf=1e9+1e6;
pair<int,int> dfs(int u){
int l=0,r=inf;
if(!ver[u].size()){
if(a[u]!=-1) l=r=a[u];
return make_pair(l,r);
}
int cnt=0;
vector<pair<int,int>> tmp;
for(auto p:ver[u]){
auto T=dfs(p);
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);
}
auto T=dfs(1);
if(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: 0
Runtime Error
input:
2