Submission #1114559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114559		thelegendary08	Jail (JOI22_jail)	C++17	66 / 100	233 ms	43136 KiB

jail

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) cout<<#v<<' '; for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 120005;
int start[mxn];
int finish[mxn];
int timer = -1;
vvi adj(mxn);
vi dfs_order;
vi depth(mxn);
vi par(mxn);
vb vis(mxn);
vb inpath(mxn);
bool cycle;
vector<set<int>> diradj(mxn);
int timer2 = -1;
int s2[mxn];
int e2[mxn];
void euler_tour(int x, int from){
	dfs_order.pb(x);
	par[x] = from;
	if(x != 1)depth[x] = depth[from] + 1;
	timer++;
	timer2++;
	start[x] = timer;
	s2[x] = timer2;
	for(auto u : adj[x]){
		if(u != from){
			euler_tour(u, x);
			dfs_order.pb(x);
			timer++;
		}
	}
	finish[x] = timer;
	e2[x] = timer2;
}

bool dfs(int node){
	//dout(node);
	if(!vis[node]){
		vis[node] = 1;
		inpath[node] = 1;
		for(auto u : diradj[node]){
			if(!vis[u] && dfs(u))return 1;
			else if(inpath[u]){
				return 1;
			}
		}
		inpath[node] = 0;
	}
	return 0;
}

pii tree[mxn * 4];
int trs;
void update(int k, int x){
	k += trs;
	tree[k] = {x,k-trs};
	for(k/=2; k>=1; k/=2){
		if(tree[k*2].first < tree[k*2 + 1].first){
			tree[k] = tree[k*2];
		}
		else tree[k] = tree[k*2 + 1];
	}
	
}
int query(int l, int r){
	//out2(l,r);
	l += trs;
	r += trs;
	pii ret = {4e18, -1};
	while(l <= r){
		if(l % 2 == 1){
			if(tree[l].first < ret.first){
				ret = tree[l];
			}
			l++;
		}
		if(r % 2 == 0){
			if(tree[r].first < ret.first){
				ret = tree[r];
			}
			r--;
		}
		l/=2;
		r/=2;
	}
	return ret.second;
}

bool is_parent(int a, int b){
	//is a a parent of b?
	return s2[b] >= s2[a] && s2[b] <= e2[a];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	int tt;
	cin>>tt;
	f0r(ttt, tt){
		in(n);
		trs = 2 * n - 1;
		timer = -1;
		timer2 = -1;
		FOR(i, 1, n+1){
			adj[i].clear();
			start[i] = 0;
			finish[i] = 0;
			s2[i] = 0;
			e2[i] = 0;
		}
		f0r(i,n-1){
			in2(a,b);
			adj[a].pb(b);
			adj[b].pb(a);
		}
		in(m);
		if(tt <= 20 && m<=500){
			FOR(i, 1, n+1)depth[i] = 0;
			FOR(i, 1, n+1)par[i] = -1;
			dfs_order.clear();
			
			vpii paths;
			vi starts(n+1, -1);
			vi ends(n+1, -1);
			
			f0r(i, m){
				in2(a,b);
				paths.pb({a,b});
				starts[a] = i;
				ends[b] = i;
			}
			euler_tour(1, -1);
			f0r(i, 2*n-1){
				update(i, depth[dfs_order[i]]);
			}
			
			f0r(i,m)diradj[i].clear();
			vi lca(m);
			f0r(i,m){
				//out2(finish[paths[i].first], start[paths[i].second]);
				if(start[paths[i].first] <= start[paths[i].second]){
					lca[i] = dfs_order[query(start[paths[i].first], start[paths[i].second])];
				}
				else{
					lca[i] = dfs_order[query(start[paths[i].second],start[paths[i].first])];
				}
			}
			//vout(lca);
			//vout(dfs_order);
			//FOR(i, 1, n+1)cout<<s2[i]<<' ';
			//cout<<'\n';
			//FOR(i, 1, n+1)cout<<e2[i]<<' ';
			//cout<<'\n';
			f0r(i,m){
				int st1 = paths[i].first;
				int en1 = paths[i].second;
				f0r(j,m){
					if(i != j){
						//check if start of j is on path, if end of j is on path
						//either par(j, start) and par(lca, j) or par(j, end) and par(lca, j)
						
						int st = paths[j].first;
						int en = paths[j].second;
						if(is_parent(lca[i], st) && (is_parent(st, st1) || is_parent(st, en1))){
							//j comes before i
							diradj[j].insert(i);
						}
						if(is_parent(lca[i], en) && (is_parent(en, st1) || is_parent(en, en1))){
							diradj[i].insert(j);
						}
						
					}
				}
			}
			/*
			f0r(i,m){
				vi path;
				int a = paths[i].first;
				int b = paths[i].second;
				vi revpath;
				while(depth[a] != depth[b]){
					if(depth[a] > depth[b]){
						path.pb(a);
						a = par[a];
					}
					else{
						revpath.pb(b);
						b = par[b];
					}
				}
				while(a != b){
					path.pb(a);
					revpath.pb(b);
					a = par[a];
					b = par[b];
				}
				path.pb(a);
				reverse(all(revpath));
				
				f0r(j, revpath.size())path.pb(revpath[j]);
				
				f0r(j, path.size()){
					if(starts[path[j]] != -1 && starts[path[j]] != i){
						diradj[starts[path[j]]].insert(i);
					}
					if(ends[path[j]] != -1 && ends[path[j]] != i){
						diradj[i].insert(ends[path[j]]);
					}
				}
				
			}
			*/
			f0r(i,m){
				//vout(diradj[i]);
			}
			
			f0r(i,m){
				vis[i] = 0;
				inpath[i] = 0;
			}
			cycle = 0;
			f0r(i,m){
				if(!vis[i]){
					bool ret = dfs(i);
					if(ret)cycle = 1;
					//out("NEXT");
				}
			}
			yn(!cycle);
			
			//vout(depth);
			//vout(par);
			//vout(dfs_order);
			/*
			vi loc(n+1);
			f0r(i, n){
				loc[dfs_order[i]] = i;
			}
			
			int spt[n][10];
			f0r(i,n)spt[i][0] = depth[dfs_order[i]];
			
			FOR(j, 1, 10){
				f0r(i, n - (1 << j) + 1){
					spt[i][j] = min(spt[i][j-1], spt[i + (1 << (j-1))][j-1]);
				}
			}
			*/
			
			
			
		}
		else{
			vpii v;
			vector<pair<pii,int>>w;
			f0r(i,m){
				in2(a,b);
				v.pb({min(a,b),max(a,b)});
				w.pb({{min(a,b),max(a,b)}, (a > b)});
			}
			sort(all(v));
			sort(all(w));
			int mx = -1;
			bool ok = 1;
			f0r(i,m){
				//out3(w[i].first.first, w[i].first.second, w[i].second);
			}
			f0r(i,m){
				if(v[i].second <= mx){
					ok = 0;
					break;
				}
				else{
					mx = v[i].second;
				}
			}
			mx = -1;
			int mx2 = -1;
			f0r(i, m){
				if(w[i].second){
					if(w[i].first.first < mx)ok = 0;
					else mx2 = w[i].first.second;
				}
				else{
					if(w[i].first.first < mx2)ok = 0;
					else mx = w[i].first.second;
				}
			}
			yn(ok);
		}
		
	}
}

• Subtask 1: 5 / 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