| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 876152 |
2023-11-21T10:22:55 Z |
Ice_man |
Jail (JOI22_jail) |
C++17 |
|
13 ms |
860 KB |
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#define maxn 1005
#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)
{
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)
{
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;
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;
}
Compilation message
jail.cpp:11:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
11 | #pragma GCC target(avx2)
| ^~~~
jail.cpp: In function 'void solve()':
jail.cpp:142:21: warning: unused variable 'lca1' [-Wunused-variable]
142 | int lca1 = get_lca(start[a] , _final[a]);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 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 |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
