| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 891097 | vjudge1 | Jail (JOI22_jail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}