QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769852#6654. 大纲ANIG#WA 41ms17952kbC++141.3kb2024-11-21 19:36:502024-11-21 19:36:50

Judging History

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

  • [2024-11-21 19:36:50]
  • 评测
  • 测评结果:WA
  • 用时:41ms
  • 内存:17952kb
  • [2024-11-21 19:36:50]
  • 提交

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=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);
		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: 7436kb

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: 29ms
memory: 7464kb

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: 41ms
memory: 17952kb

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

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'