oj.uz

Submission #1114133

# Submission time Handle Problem Language Result Execution time Memory
1114133 2024-11-18T08:31:09 Z thelegendary08 Jail (JOI22_jail) C++17
0 / 100
 11 ms 592 KB 
#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 = 255;
int start[mxn];
int finish[mxn];
int timer = 0;
vvi adj(mxn);
vb vis(mxn);
vi dfs_order;
vi depth(mxn);
vi par(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;
}
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)vis[i] = 0;
			FOR(i, 1, n+1)depth[i] = 0;
			FOR(i, 1, n+1)par[i] = -1;
			dfs_order.clear();
			
			vpii paths;
			f0r(i, m){
				in2(a,b);
				paths.pb({a,b});
			}
			euler_tour(1, -1);
			//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]);
				}
			}
			*/
			
			bool ans = 1;
			//vout(depth);
			//vout(par);
			f0r(i, m){
				FOR(j, i+1, m){
					//construct path i
					
					int s1 = paths[i].first;
					int e1 = paths[i].second;
					/*
					int lg = floor(log2(e1 - s1 + 1));
					int mnd = min(spt[s1][lg], spt[e1 - (1 << lg) + 1][lg]);
					*/
					//dout(mnd);
					vi p1;
					vi tmp;
					
					while(depth[s1] != depth[e1]){
						if(depth[s1] > depth[e1]){
							p1.pb(s1);
							s1 = par[s1];
						}
						else{
							tmp.pb(e1);
							e1 = par[e1];
						}
					}
					while(s1 != e1){
						p1.pb(s1);
						tmp.pb(e1);
						s1 = par[s1];
						e1 = par[e1];
					}
					p1.pb(s1);
					
					reverse(all(tmp));
					for(auto u : tmp)p1.pb(u);
					
					//construct path j
					s1 = paths[j].first;
					e1 = paths[j].second;
					/*
					int lg = floor(log2(e1 - s1 + 1));
					int mnd = min(spt[s1][lg], spt[e1 - (1 << lg) + 1][lg]);
					*/
					//dout(mnd);
					vi p2;
					vi tmp2;
					
					while(depth[s1] != depth[e1]){
						if(depth[s1] > depth[e1]){
							p2.pb(s1);
							s1 = par[s1];
						}
						else{
							tmp2.pb(e1);
							e1 = par[e1];
						}
					}
					while(s1 != e1){
						p2.pb(s1);
						tmp2.pb(e1);
						s1 = par[s1];
						e1 = par[e1];
					}
					p2.pb(s1);
					
					reverse(all(tmp2));
					for(auto u : tmp2)p2.pb(u);
					//vout(p1);
					//vout(p2);
					
					//now check if the paths are ok
					vector<set<int>> deg(n+1);
					f0r(k, p1.size() - 1){
						deg[p1[k]].insert(p1[k+1]);
						deg[p1[k+1]].insert(p1[k]);
					}
					f0r(k, p2.size() - 1){
						deg[p2[k]].insert(p2[k+1]);
						deg[p2[k+1]].insert(p2[k]);
					}
					
					bool branch = 0;
					f0r(k, n+1){
						//cout<<deg[k].size()<<' ';
						if(deg[k].size() > 2)branch = 1;
					}
					//cout<<'\n';
					if(!branch){
						if(find(all(p1), p2[0]) != p1.end() && find(all(p1), p2[p2.size() - 1]) != p1.end()){
							ans = 0;
						}
						else{
							vi nxt(n+1);
							f0r(k, p1.size() - 1){
								nxt[p1[k]] = p1[k+1];
							}
							//vout(nxt);
							f0r(k, p2.size() - 1){
								if(nxt[p2[k+1]] == p2[k])ans = 0;
							}
						}
					}
					
				}
			}
			yn(ans);
			
			
		}
		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

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++)
......
  171 |      f0r(k, p1.size() - 1){
      |          ~~~~~~~~~~~~~~~~      
jail.cpp:171:6: note: in expansion of macro 'f0r'
  171 |      f0r(k, p1.size() - 1){
      |      ^~~
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++)
......
  175 |      f0r(k, p2.size() - 1){
      |          ~~~~~~~~~~~~~~~~      
jail.cpp:175:6: note: in expansion of macro 'f0r'
  175 |      f0r(k, p2.size() - 1){
      |      ^~~
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++)
......
  192 |        f0r(k, p1.size() - 1){
      |            ~~~~~~~~~~~~~~~~    
jail.cpp:192:8: note: in expansion of macro 'f0r'
  192 |        f0r(k, p1.size() - 1){
      |        ^~~
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++)
......
  196 |        f0r(k, p2.size() - 1){
      |            ~~~~~~~~~~~~~~~~    
jail.cpp:196:8: note: in expansion of macro 'f0r'
  196 |        f0r(k, p2.size() - 1){
      |        ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 11 ms 484 KB Output is correct
6 Incorrect 2 ms 592 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 11 ms 484 KB Output is correct
6 Incorrect 2 ms 592 KB Output isn't correct
7 Halted 0 ms 0 KB -