QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769863#6654. 大纲ANIG#WA 30ms7452kbC++141.3kb2024-11-21 19:39:512024-11-21 19:39:51

Judging History

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

  • [2024-11-21 19:39:51]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:7452kb
  • [2024-11-21 19:39:51]
  • 提交

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'