Submission #1114521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114521		thelegendary08	Jail (JOI22_jail)	C++17	54 / 100	63 ms	22684 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 = 0;
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);
void euler_tour(int x, int from){
	//dfs_order.pb(x);
	par[x] = from;
	if(x != 1)depth[x] = depth[from] + 1;
	//timer++;
	//start[x] = timer;
	for(auto u : adj[x]){
		if(u != from)euler_tour(u, x);
		dfs_order.pb(x);
	}
	//finish[x] = timer;
}

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;
}
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);
		FOR(i, 1, n+1)adj[i].clear();
		f0r(i,n-1){
			in2(a,b);
			adj[a].pb(b);
			adj[b].pb(a);
		}
		in(m);
		if(tt <= 20 && n <= 250 && m <= 100){
			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,m)diradj[i].clear();
			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);
		}
		
	}
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
  129 |     f0r(j, revpath.size())path.pb(revpath[j]);
      |         ~~~~~~~~~~~~~~~~~      
jail.cpp:129:5: note: in expansion of macro 'f0r'
  129 |     f0r(j, revpath.size())path.pb(revpath[j]);
      |     ^~~
jail.cpp:11:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define f0r(i,n) for(int i=0;i<n;i++)
......
  131 |     f0r(j, path.size()){
      |         ~~~~~~~~~~~~~~         
jail.cpp:131:5: note: in expansion of macro 'f0r'
  131 |     f0r(j, path.size()){
      |     ^~~

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