| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 876835 |
2023-11-22T12:10:37 Z |
Ice_man |
Jail (JOI22_jail) |
C++14 |
|
29 ms |
14684 KB |
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#define maxn 120005
#define maxlog 20
#define pb(x) push_back(x)
#define control cout<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops")
#pragma GCC target(avx2)
using namespace std;
int n, m, q;
vector <int> v[maxn];
int start[maxn], _final[maxn];
vector <int> new_tree[maxn];
int bin_lift[maxn][maxlog];
int pom1[maxn];
int pom2[maxn];
int chain[maxn];
void read()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < maxlog; j++) bin_lift[i][j] = 0;
}
for(int i = 1; i <= n * 12; i++)
{
pom1[i] = 0;
pom2[i] = 0;
v[i].clear();
new_tree[i].clear();
}
int from, to;
for(int i = 1; i <= (n - 1); i++)
{
cin >> from >> to;
v[from].pb(to);
v[to].pb(from);
}
cin >> m;
for(int i = 1; i <= m; i++)
{
pom1[i] = 0;
pom2[i] = 0;
}
for(int i = 1; i <= m; i++) cin >> start[i] >> _final[i];
}
int tree[12 * maxn];
void build_seg(int node , int l , int r)
{
if(l == r)
{
tree[l] = node;
return;
}
int mid = (r - l) / 2 + l;
build_seg(node * 2 , l , mid);
build_seg(node* 2 + 1 , mid + 1 , r);
new_tree[node].pb(node * 2);
new_tree[node].pb(node * 2 + 1);
new_tree[node * 2 + 4 * n].pb(node + 4 * n);
new_tree[node * 2 + 1 + 4 * n].pb(node + 4 * n);
}
void _add(int node , int l , int r , int ql , int qr , int val)
{
if(ql <= l && r <= qr)
{
new_tree[node + n * 4].pb(val + n * 8);
new_tree[node + n * 8].pb(node);
return;
}
if(qr < l || r < ql) return;
int mid = (r - l) / 2 + l;
_add(node * 2 , l , mid , ql , qr , val);
_add(node * 2 + 1 , mid + 1 , r , ql , qr , val);
}
///int bin_lift[maxn][maxlog];
int depth[maxn];
int subtree[maxn];
int help[maxn * 12];
void calc_bin(int node, int parent)
{
for(int nb : v[node])
{
if(nb != parent)
{
bin_lift[nb][0] = node;
for(int i = 1; i < maxlog; i++) bin_lift[nb][i] = bin_lift[bin_lift[nb][i - 1]][i - 1];
depth[nb] = depth[node] + 1;
calc_bin(nb, node);
subtree[node] += subtree[nb];
if(subtree[v[node][0]] < subtree[nb] || v[node][0] == parent) swap(v[node][0] , nb);
}
}
}
int get_lca(int a, int b)
{
if(depth[a] < depth[b]) swap(a, b);
///cout << a << "-" << b << endl;
int levels = depth[a] - depth[b];
///cout << "** " << levels << endl;;
for(int i = maxlog - 1; i >= 0; i--)
{
if(levels >> i & 1)
{
///cout << ">< "<< (1 << i) << endl;
a = bin_lift[a][i];
///levels -= (1 << i);
///cout << (1 << i) << endl;
}
}
///cout << a << "-" << b << endl;
if(a == b) return a;
for(int i = maxlog - 1; i >= 0; i--)
{
if(!bin_lift[a][i]) continue;
if(!bin_lift[b][i]) continue;
if(bin_lift[a][i] != bin_lift[b][i])
{
a = bin_lift[a][i];
b = bin_lift[b][i];
}
}
return bin_lift[a][0];
}
int heads[maxn];
void add_edges(int node , int from , int to)
{
bool lamp1 = true;
bool lamp2 = true;
while(heads[from] != heads[to])
{
///cout << from << " " << to << endl;
if(heads[from] == heads[to]) break;
if(depth[heads[to]] > depth[heads[from]])
{
swap(from , to);
swap(lamp1 , lamp2);
}
_add(1 , 1 , n , chain[heads[from]] , chain[from] - lamp1 , node);
lamp1 = false;
from = bin_lift[heads[from]][0];
}
if(chain[from] > chain[to])
{
swap(from , to);
swap(lamp1 , lamp2);
}
_add(1 , 1 , n , chain[from] + lamp1 , chain[to] - lamp2 , node);
}
bool check(int a, int b, int c)
{
int lca = get_lca(a, b);
///int pom = get_lca(lca , c);
if(get_lca(lca, c) == lca && get_lca(c, a) == c) return true;
if(get_lca(lca, c) == lca && get_lca(c, b) == c) return true;
return false;
}
int cur_chain = 0;
///int heads[maxn];
void dfs_hld(int node , int parent , int leader)
{
cur_chain++;
chain[node] = cur_chain;
heads[node] = leader;
if(v[node][0] != parent) dfs_hld(v[node][0] , node , leader);
for(int nb : v[node]) if(nb != parent && nb != v[node][0])
{
dfs_hld(nb , node , nb);
}
}
//vector <int> new_tree[maxn];
void solve()
{
calc_bin(1, 0);
///control
/**for(int a = 1; a <= m; a++)
{
for(int b = 1; b <= m; b++)
{
if(a == b) continue;
///int lca1 = get_lca(start[a], _final[a]);
if(check(start[a], _final[a], start[b]) == true) new_tree[b].pb(a);
if(check(start[a], _final[a], _final[b]) == true) new_tree[a].pb(b);
///cout << check(start[a] , _final[a] , start[b]) << " " << check(start[a] , _final[a] , _final[b]) << endl;
}
}*/
cur_chain = 0;
///_time = 0;
dfs_hld(1 , 0 , 1);
/**cout << "--------------" << endl;
for(int i = 1; i <= n; i++) cout << heads[i] << " ";
cout << endl << "--------------" << endl;*/
///control
build_seg(1 , 1 , n);
///cout << "sd;inkmsad" << endl;
///control
for(int i = 1; i <= n * 12; i++) help[i] = 0;
for(int i = 1; i <= m; i++)
{
new_tree[tree[chain[_final[i]]]].pb(8 * n + i);
new_tree[i + n * 8].pb(n * 4 + tree[chain[start[i]]]);
help[_final[i]] = i;
add_edges(i , start[i] , _final[i]);
///cout << "passed " << i << endl;
}
///cout << "-----------------" << endl;
///control
for(int i = 1; i <= m; i++) if(help[start[i]])
{
new_tree[i + 8 * n].pb(help[start[i]] + 8 * n);
}
/**for(int i = 1; i <= n; i++)
{
cout << i << ": ";
for(int nb : new_tree[i]) cout << nb << " ";
cout << endl;
}*/
}
stack <int> s;
///int pom1[maxn] , pom2[maxn];
int _time = 0;
int br = 0;
bool ans = true;
void count_ssc(int node, int parent)
{
s.push(node);
_time++;
pom1[node] = _time;
pom2[node] = _time;
for(int nb : new_tree[node])
{
if(pom2[nb] == -1) continue;
if(pom2[nb])
{
pom1[node] = min(pom1[node], pom1[nb]);
}
else
{
count_ssc(nb, node);
pom1[node] = min(pom1[node], pom1[nb]);
}
}
int h;
if(pom1[node] == pom2[node])
{
br++;
h = 0;
while(!s.empty() && s.top() != node)
{
pom2[s.top()] = -1;
h += s.top() > 8 * n? 1 : 0;
s.pop();
}
h += node > 8 * n? 1 : 0;
pom2[node] = -1;
if(h > 1) ans = false;
s.pop();
}
}
int _pom[maxn];
void combine()
{
cin >> q;
while(q--)
{
br = 0;
_time = 0;
ans = true;
read();
///control
solve();
///control
/**for(int i = 1; i <= n; i++)
{
cout << i << ": ";
for(int power = 0; power < maxlog; power++)
{
cout << bin_lift[i][power] << " ";
}
cout << endl;
}*/
///cout << "-> " << get_lca(1 , 5) << endl;
while(s.size()) s.pop();
for(int i = 1; i <= 12 * n + m; i++) if(!pom2[i]) count_ssc(i, -1);
if(ans == true) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
int main()
{
/**ios_base::sync_with_stdio(false);
cin.tie(nullptr);*/
combine();
return 0;
}
/**
3
3
1 2
2 3
2
2 1
3 2
7
1 2
2 3
3 4
4 5
5 6
6 7
3
1 3
4 2
2 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8
*/
Compilation message
jail.cpp:12:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
12 | #pragma GCC target(avx2)
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
14684 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 5 |
Incorrect |
16 ms |
14396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14172 KB |
Output is correct |
| 4 |
Incorrect |
29 ms |
14684 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
