Submission #609634

#	Time	Username	Problem	Language	Result	Execution time	Memory
609634		HamletPetrosyan	Jail (JOI22_jail)	C++17	61 / 100	5054 ms	51796 KiB

jail

/// #if (code == true)

#include <bits/stdc++.h>
using namespace std;

#define pll pair<long long, long long>
#define len(a) ((int)((a).size()))
#define all(a) a.begin(), a.end()
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 2e5 + 5;

ll n, m, s[N], t[N];
vector<int> g[N], dir[N];
int color[N];

ll ls[N][25], tin[N], tout[N], timer = 0;

void dfs(int v, int p){
	ls[v][0] = p;
	for(int i = 1; i <= 20; i++){
		ls[v][i] = ls[ls[v][i - 1]][i - 1];
	}

	tin[v] = ++timer;
	for(int i = 0; i < len(g[v]); i++){
		int to = g[v][i];
		if(to == p) continue;
		dfs(to, v);
	}
	tout[v] = ++timer;
}

bool isa(int a, int b){
	return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

int lsa(int a, int b){
	if(isa(a, b)) return a;
	if(isa(b, a)) return b;
	for(int i = 20; i >= 0; i--){
		if(isa(ls[a][i], b)) continue;
		a = ls[a][i];
	}
	return ls[a][0];
}

void check(int i, int j){
	int a = lsa(s[i], t[i]);
	int b = lsa(s[j], t[j]);
	if(isa(a, s[j]) && (isa(s[j], s[i]) || isa(s[j], t[i]))){
		dir[i].add(j);
	}
	if(isa(b, t[i]) && (isa(t[i], s[j]) || isa(t[i], t[j]))){
		dir[i].add(j);
	}
}

bool check_cycle(int v){
	color[v] = 1;
	for(int i = 0; i < len(dir[v]); i++){
		int to = dir[v][i];
		if(color[to] == 2) continue;
		if(color[to] == 1) {
			return true;
		}
		if(check_cycle(to)){
			return true;
		}
	}
	color[v] = 2;
	return false;
}

void solve(){
	timer = 0;

	cin >> n;
	for(int i = 1; i <= n; i++){
		g[i].clear();
	}
	for(int i = 0; i < m; i++){
		dir[i].clear();
		color[i] = 0;
	}

	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		g[u].add(v);
		g[v].add(u);
	}
	dfs(1, 1);
	cin >> m;
	for(int i = 0; i < m; i++){
		cin >> s[i] >> t[i];
	}

	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			if(i == j) continue;
			check(i, j);
		}
	}
	for(int i = 0; i < m; i++){
		if(color[i] == 0) {
			if(check_cycle(i)){
				cout << "No\n";
				return;
			}
		}
	}

	cout << "Yes\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(15);

	cin >> _ ;
	while(_--) solve();
	return 0;
}

/// #else
/// #include <bits/stdc++.h> using namespace std; int main() { cout << "Hello World!"; }
/// #endif

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23