| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 876175 |
2023-11-21T10:54:10 Z |
Ice_man |
Jail (JOI22_jail) |
C++14 |
|
12 ms |
860 KB |
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#define maxn 10005
#define maxlog 20
#define pb(x) push_back(x)
#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];
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; i++)
{
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 bin_lift[maxn][maxlog];
int depth[maxn];
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);
}
}
}
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 >= 1; 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];
}
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;
}
//vector <int> new_tree[maxn];
void solve()
{
calc_bin(1, 0);
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);
else 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;
}
}
/**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;
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]);
}
}
if(pom1[node] == pom2[node])
{
br++;
while(!s.empty() && s.top() != node)
{
pom2[s.top()] = -1;
s.pop();
}
pom2[node] = -1;
s.pop();
}
}
void combine()
{
cin >> q;
while(q--)
{
br = 0;
_time = 0;
read();
solve();
/**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 <= m; i++) if(!pom2[i]) count_ssc(i, -1);
if(br == m) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
combine();
return 0;
}
/**
1
2
1 2
2
1 2
2 1
*/
Compilation message
jail.cpp:11:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
11 | #pragma GCC target(avx2)
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
860 KB |
Output is correct |
| 2 |
Correct |
0 ms |
860 KB |
Output is correct |
| 3 |
Correct |
0 ms |
856 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
0 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
0 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
0 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
0 ms |
860 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
860 KB |
Output is correct |
| 2 |
Correct |
0 ms |
860 KB |
Output is correct |
| 3 |
Correct |
0 ms |
860 KB |
Output is correct |
| 4 |
Correct |
0 ms |
860 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
860 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
860 KB |
Output is correct |
| 2 |
Correct |
0 ms |
860 KB |
Output is correct |
| 3 |
Correct |
0 ms |
856 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
