Submission #860690

#	Time	Username	Problem	Language	Result	Execution time	Memory
860690		Iliya_	Jail (JOI22_jail)	C++14	0 / 100	10 ms	33372 KiB

jail

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
using namespace std;
typedef long long ll; 

const int N = 2e5+7, NN = 507, lg = 23; 
int mark[N], par[lg][N], h[N], tim[N][2], now, dat[N][2], ind[N], dp1[N], dp2[N];
vector<int> g[N], make[N], to;

void dfs(int v, int fa){
	tim[v][0] = ++now; 
	h[v] = h[fa] + 1; 
	par[0][v] = fa; 
	for(ll i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]];
	for(int u : g[v]){
		if (u == fa) continue;
		dfs(u,v);
	}
	tim[v][1] = ++now;
}

void dfs2(int v){
	mark[v] = 1;
	for(int u : make[v]){
		if (mark[u]) continue; 
		dfs2(u); 
	}
	to.push_back(v); 
}

bool ispar(int v, int u){
	if (tim[v][0] <= tim[u][0] && tim[v][1] >= tim[u][1]) return 1; 
	else return 0;
}

int lca(int v, int u){
	if (v == u) return v; 
	if (h[v] < h[u]) swap(v,u);
	int dif = h[v] - h[u]; 
	for(int i=lg-1; i>=0; i--){
		if ((dif>>i)&1) v = par[i][v]; 
	}
	if (v == u) return v; 
	for(int i=lg-1; i>=0; i--){
		if (par[i][v] != par[i][u]){
			v = par[i][v]; 
			u = par[i][u]; 
		}
	}
	return par[0][v]; 
}

bool inway(int v, int u, int w){
	int lc = lca(v,u); 
	if ((ispar(w,v) && ispar(lc,w)) || (ispar(w,u) && ispar(lc,w))) return 1; 
	else return 0;
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t; cin >> t; 
	while(t--){
		int n; cin >> n; 
		for(int i=1; i<=n; i++){
			g[i].clear(); 
			for(ll j=0; j<lg; j++) par[j][i] = 0; 
		}
		bool mas = true; 
		for(int i=1; i<n; i++){
			int v,u; cin >> v >> u; 
			g[v].push_back(u); 
			g[u].push_back(v); 
			if (v != i || u != i+1) mas = false;  
		}
		if (mas){
			for(int i=0; i<=n+1; i++) dp1[i] = dp2[i] = 0; 
			int m; cin >> m; 
			for(int i=1; i<=m; i++){
				int st,en; cin >> st >> en;
				if (st < en){
					dp1[st]++; 
					dp1[en+1]--;
				}
				else{
					dp2[st]++;
					dp2[en-1]--;
				}
			}
			for(int i=1; i<=n; i++) dp1[i] += dp1[i-1]; 
			for(int i=n; i>=1; i--) dp2[i] += dp2[i+1];
			bool ans = true; 
			for(int i=1; i<=n; i++) if (dp1[i] && dp2[i]) ans = false; 
			cout << (ans ? "Yes" : "No") << endl;
			continue; 
		}
		now = 0; 
		dfs(1,0); 
		int m; cin >> m; 
		for(int i=1; i<=m; i++){
			make[i].clear(); 
			mark[i] = 0; 
			ind[i] = 0;
		}
		for(int i=1; i<=m; i++) cin >> dat[i][0] >> dat[i][1];
		for(int i=1; i<=m; i++){
			for(int j=1; j<=m; j++){
				if (j == i) continue; 
				int s1 = dat[i][0], t1 = dat[i][1], s2 = dat[j][0], t2 = dat[j][1];
				if (inway(s1,t1,s2) || inway(s2,t2,t1)) make[j].push_back(i); 
			}
		}
		to.clear(); 
		for(int i=1; i<=m; i++){
			if (!mark[i]) dfs2(i); 
		}
		reverse(to.begin(),to.end());
		for(int i=0; i<int(to.size()); i++) ind[to[i]] = i;
		bool ans = true; 
		for(int i=1; i<=m; i++){
			for(int cur : make[i]){
				if (ind[cur] < ind[i]) ans = false; 
			}
		}
		cout << (ans ? "Yes" : "No") << endl;
	}  

	return 0;
}

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