Submission #891097

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891097	2023-12-22T07:36:32 Z	vjudge1	Jail (JOI22_jail)	C++17	Compilation error	0 ms	0 KB

jail

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 998244353;
const int N = 1e5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
#define ar array
/*
1
5

* */


1
10
1 2
1 3
1 7
3 4
3 5
5 6
7 8
7 9
7 10
2
2 4
5 1

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	
	auto F = [&](int n, int q, vector<pair<int, int> > query){
		vector<int> p(q);
		for(int i = 0;i < q; i++) p[i] = i;
		do{
			vector<int> used(n+1, 0);
			for(int i : p){
				used[query[i].ff]++;
			}
			int ok = 1;
			for(int i : p){
				used[query[i].ff]--;
				for(int j = min(query[i].ff, query[i].ss); j <= max(query[i].ff, query[i].ss); j++){
					if(used[j]){
						ok = 0;
						break;
					}
				}
				
				used[query[i].ss]++;
			}
			if(ok){
				return 1;
			}
		}while(next_permutation(all(p)));
		return 0;
	};
	
	auto G = [&](int n, int q, vector<pair<int, int> > query, vector< vector<pair<int, int> > > g){
		
		 vector<int> edge1(n+1, 0), edge2(n+1, 0);
		 vector<int> par_index(n+1, 0);
		vector<int> sub(n + 1, 0), depth(n + 1, 0);
		vector<int> tin(n + 1), tout(n + 1);
		int timer = 1;
		int up[n+1][18];
		function<void(int, int)> dfs=[&](int v, int par){
			tin[v] = timer++;
			up[v][0] = par;
			for(int j = 1;j < 18; j++){
				up[v][j] = up[up[v][j-1]][j-1];
			}
			sub[v]+= 1;
			for(auto [to, idx] : g[v]){
				if(to == par) continue;
				depth[to] = depth[v] + 1;
				par_index[to] = idx;
				dfs(to, v);
				sub[v]+= sub[to];
			}
			tout[v] = timer;
		};	
		dfs(1, 1);
		auto lca = [&](int a, int b){
			if(depth[a] > depth[b]) swap(a, b);
			int k = depth[b] - depth[a];
			for(int i = 0;i < 18; i++){
				if(k & (1<<i)){
					b = up[b][i];
				}
			}
			if(a == b) return a;
			for(int i = 17; i >= 0; i--){
				if(up[a][i] != up[b][i]){
					a = up[a][i];
					b = up[b][i];
				}
			}
			return up[a][0];
		};

		
		
		auto go = [&](int a, int p, int type){
			int QQ = n+1;
			while(a != p){
				QQ--;
				if(QQ == 0){
					assert(false);
				}
				int idx = par_index[a];
				if(type == 1) edge1[idx] = 1;
				else edge2[idx] = 1;
				a = up[a][0];
			}
		};
		auto check=[&](int a, int p, int type){
		while(a != p){
			int idx = par_index[a];
			if(type == 1){
				if(edge2[idx]) return 0;
			} 
			else{
				if(edge1[idx]) return 0;
			} 
			a = up[a][0];
		}
		return 1;
	};
		for(int i = 0;i < q; i++){
			for(int k = 1; k < n; k++){
				edge1[k] = 0;
				edge2[k] = 0;
			}
			auto [a, b] = query[i];
			int lc = lca(a, b);
			go(a, lc, 1);
			go(b, lc, 2);
			for(int j = 0;j < q; j++){
				if(i == j) continue;
				auto [a1, b1] = query[j];
				int lc1 = lca(a1, b1);
				
				int ok = 1, ok1 = 1;
				
				if(!check(b1, lc1, 2)){
					ok = 0;
				}
				if(!check(a1, lc1, 1)){
					ok = 0;
				}
				if(!ok){
					return 0;
				}
			}
		}
		
		
		
		for(int i = 0;i < q; i++){
			for(int j = 0; j < q; j++){
				if(i == j) continue;
				auto [a, b] = query[i];
				auto [a1, b1] = query[j];
				int lc = lca(a, b);
				int lc1 = lca(a1, b1);
				
				for(int k = 1; k < n; k++) edge1[k] = 0;
				
				go(a, lc, 1);
				go(b, lc, 1);
				int ok = 1;
				int QQ = n+1;
				while(a1 != lc1){
					QQ--;
					if(QQ == 0){
						assert(false);
					}
					int idx = par_index[a1];
					if(!edge1[idx]){
						ok = 0;
						break;
					}
					a1 = up[a1][0];
				}
				QQ = n+1;
				while(b1 != lc1){
					QQ--;
					if(QQ == 0){
						assert(false);
					}
					int idx = par_index[b1];
					if(!edge1[idx]){
						ok = 0;
						break;
					}
					b1 = up[b1][0];
				}
				
				if(ok){
					return 0;
				}
				
				
			}
		}
		
		
		
		return 1;
	};
	
	int t = rnd(3, 10);
	while(t--){
		int n = rnd(2, 8);
		 vector< vector< pair<int, int> > > g(n+1);
		for(int i = 1;i < n; i++){
			g[i].push_back({i+1, i});
			g[i+1].push_back({i, i});
		//	cout << i << ' ' << i+1 << '\n';
		}
		int q = rnd(1, 2); 
		set<pair<int, int> > st;
		for(int i = 1;i <= n; i++){
			st.insert({i, i});
		}
		set<int> A, B;
		vector< pair<int, int> > qu;
		for(int i = 1;i <= q; i++){
			int a, b;
			while(true){
				 a = rnd(1, n);
				 b = rnd(1, n); 
				 if(A.count(a) == false && B.count(b) == false){
					if(st.count({a, b}) == false) break;
				}
			}
			st.insert({a, b});
			A.insert(a);
			B.insert(b);
			qu.push_back({a, b});
		}
		int FF = F(n, q, qu);
		int GG = G(n, q, qu, g);
		if(FF != GG){
			cout << "For this test : " << '\n';
			cout << n << '\n';
			cout << q << '\n';
			for(int i = 0;i < q; i++){
				cout << qu[i].ff << ' ' << qu[i].ss << '\n';
			}
			
			cout << '\n';
			cout << "Expected : " << FF << '\n';
			cout << "Yours : " << GG << '\n';
			return 0;
		}
	}
	return 0;
}

Compilation message

jail.cpp:20:1: error: expected unqualified-id before numeric constant
   20 | 1
      | ^