Submission #891091

#	Time	Username	Problem	Language	Result	Execution time	Memory
891091		vjudge1	Jail (JOI22_jail)	C++17	0 / 100	2 ms	4188 KiB

jail

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const long long N = 1e5+50, inf = 1e18, mod = 1e9+7;
vi g[N];
int pre[N];
int timer;
int tin[N], tout[N];
int up[20][N];
void dfs(int v, int pr) {
	//~ cout << pr << ' ' << v << '\n';
	pre[v] = pr;
    tin[v] = ++timer;
    up[0][v] = pr;
    for (int i = 1; i <= 18; i++) {
        up[i][v] = up[i - 1][ up[i - 1][v] ];
    }
    for (int to : g[v]) {
        if (to == pr) continue;
        dfs(to, v);
    }
    tout[v] = timer;
}

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

int lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 18; i >= 0; i--) {
        if (!upper(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}
vi path(int s, int t){
	int h = lca(s, t);
	vi ans;
	while(s!=h){
		ans.pb(s);
		s = pre[s];
	}
	ans.pb(h);
	vi res;
	while(t!=h){
		res.pb(t);
		t = pre[t];
	}
	reverse(all(res));
	for(auto i:res)ans.pb(i);
	return ans;
}
void solve(){
	int n;
	cin >> n;
	bool ok = 1;
	for(int i = 1; i <= n; i++)g[i].clear();
	for(int i = 0; i < n-1; i++){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
		if(a != i+1 || b != i+2)ok = 0;
	}
	if(ok){
		int m;
		cin >> m;
		vii p(m);
		for(auto &[i, j]:p)cin >> i >> j;
		sort(all(p));
		set<int> st;
		for(int i = m-1; i >= 0; i--){
			if(!st.empty() && *st.begin() < p[i].ss){
				cout << "No\n";
				return;
			}
			st.insert(p[i].ss);
		}
		return;
	}
	dfs(1, -1);
	int m;
	cin >> m;
	vi ps[m], str, it;
	for(int i = 0; i < m; i++){
		int s, t;
		cin >> s >> t;
		ps[i] = path(s, t);
		str.pb(s);
		it.pb(i);
	}
	do{
		int us[n+1]{};bool ok = 1;
		for(auto i:str)us[i] = 1;
		for(int i = 0; i < m; i++){
			us[str[it[i]]] = 0;
			for(auto j:ps[it[i]]){
				if(us[j]==1){
					ok=0;
					break;
				}
			}
			us[ps[it[i]].back()]++;
			if(!ok)break;
		}
		if(ok){
			cout << "Yes\n";
			return;
		}
	}while(next_permutation(all(it)));
	cout << "No\n";
}
main(){
	//~ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

jail.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main(){
      | ^~~~

• 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