Submission #890915

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
890915	2023-12-22T05:12:27 Z	vjudge1	Jail (JOI22_jail)	C++17	0 / 100	5000 ms	15308 KB

jail

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 120000;

vector<int> g[N+1];
int n;

/*
struct Fenwick{
	vector<int> fenw;
	int n;
	
	Fenwick(int sz){
		n = sz;
		fenw.resize(n+5, 0);
	};
	
	void add(int i, int x){
		for(; i <= n; i+= i & -i){
			fenw[i]+= x;
		}
	}
	int pref(int i){
		int s = 0;
		for(; i > 0; i-= i & -i){
			s+= fenw[i];
		}
		return s;
	}
	int sum(int l, int r){
		return pref(r) - pref(l-1);
	}
	
};

*/
void cl(){
	for(int i = 1;i <= n; i++) g[i].clear();
}






void solve(){
	 cin >> n;
	
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int q; cin >> q;
	vector< pair<int, int> > query(q);
	vector<vector<pair<int, int> > > starts(n+1);
	for(int i = 0;i < q; i++){
		cin >> query[i].ff >> query[i].ss;
		starts[query[i].ff].push_back({query[i].ss, i});
	}
	for(int i = 0;i < q; i++){
		for(int j = 0;j < q; j++){
			if(i == j) continue;
			if(query[i].ff < query[i].ss && query[j].ss < query[j].ff){
				if(query[i].ss >= query[j].ss && query[i].ss <= query[j].ff){
					cout << "No";
					return;
				}
				if(query[j].ss >= query[i].ff && query[j].ss <= query[i].ss){
					cout << "No";
					return;
				}
			}
		}
	}
	for(int i = 0;i < q; i++){
		for(int j = query[i].ff; j <= query[i].ss; j++){
			for(auto [ends, pos] : starts[j]){
				if(pos == i) continue;
				if(ends < query[i].ff){
					cout << "No";
					return;
				}
				if(ends > query[i].ff && ends < query[i].ss){
					cout << "No";
					return;
				}
			}
		}
		for(int j = query[i].ff; j >= query[i].ss; j--){
			for(auto [ends, pos] : starts[j]){
				if(pos == i) continue;
				if(ends > query[i].ss && ends < query[i].ff){
					cout << "No";
					return;
				}
				if(ends > query[i].ss){
					cout << "No";
					return;
				}
			}
		}
	}
	cout << "Yes";
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--){
		solve();
		cl();
		cout << '\n';
	}
	
	return 0;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3164 KB	Output is correct
2	Correct	1 ms	3164 KB	Output is correct
3	Correct	1 ms	3164 KB	Output is correct
4	Correct	6 ms	3284 KB	Output is correct
5	Correct	11 ms	3164 KB	Output is correct
6	Correct	1 ms	3164 KB	Output is correct
7	Correct	1 ms	3164 KB	Output is correct
8	Correct	2 ms	3164 KB	Output is correct
9	Correct	20 ms	3644 KB	Output is correct
10	Correct	81 ms	9820 KB	Output is correct
11	Correct	4 ms	3160 KB	Output is correct
12	Correct	18 ms	3164 KB	Output is correct
13	Correct	2023 ms	12192 KB	Output is correct
14	Correct	103 ms	12084 KB	Output is correct
15	Correct	32 ms	12124 KB	Output is correct
16	Correct	44 ms	15308 KB	Output is correct
17	Execution timed out	5012 ms	12624 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3160 KB	Output is correct
2	Correct	1 ms	3164 KB	Output is correct
3	Correct	1 ms	3164 KB	Output is correct
4	Incorrect	1 ms	3164 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3160 KB	Output is correct
2	Correct	1 ms	3164 KB	Output is correct
3	Correct	1 ms	3164 KB	Output is correct
4	Incorrect	1 ms	3164 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3160 KB	Output is correct
2	Correct	1 ms	3164 KB	Output is correct
3	Correct	1 ms	3164 KB	Output is correct
4	Incorrect	1 ms	3164 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3160 KB	Output is correct
2	Correct	1 ms	3164 KB	Output is correct
3	Correct	1 ms	3164 KB	Output is correct
4	Incorrect	1 ms	3164 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3164 KB	Output is correct
2	Correct	1 ms	3164 KB	Output is correct
3	Correct	1 ms	3164 KB	Output is correct
4	Correct	1 ms	3164 KB	Output is correct
5	Correct	4 ms	3280 KB	Output is correct
6	Incorrect	1 ms	3160 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #7

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3164 KB	Output is correct
2	Correct	1 ms	3164 KB	Output is correct
3	Correct	1 ms	3164 KB	Output is correct
4	Correct	6 ms	3284 KB	Output is correct
5	Correct	11 ms	3164 KB	Output is correct
6	Correct	1 ms	3164 KB	Output is correct
7	Correct	1 ms	3164 KB	Output is correct
8	Correct	2 ms	3164 KB	Output is correct
9	Correct	20 ms	3644 KB	Output is correct
10	Correct	81 ms	9820 KB	Output is correct
11	Correct	4 ms	3160 KB	Output is correct
12	Correct	18 ms	3164 KB	Output is correct
13	Correct	2023 ms	12192 KB	Output is correct
14	Correct	103 ms	12084 KB	Output is correct
15	Correct	32 ms	12124 KB	Output is correct
16	Correct	44 ms	15308 KB	Output is correct
17	Execution timed out	5012 ms	12624 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-