| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 633701 |
2022-08-23T05:51:09 Z |
S2speed |
Jail (JOI22_jail) |
C++17 |
|
117 ms |
238056 KB |
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
const ll maxn = 1.2e5 + 17 , maxv = 5e6 + 17 , md = 1e9 + 7 , inf = 2e16;
vector<ll> adj[maxv] , jda[maxv] , tdj[maxn] , f;
ll jad[maxn][20] , dis[maxn] , dep = 0 , lb[maxn][20][2] , o;
ll a[maxn] , b[maxn] , c[maxn] , k;
bitset<maxv> mark;
void lDFS(ll r , ll par){
dis[r] = dep++;
lb[r][0][0] = o++;
lb[r][0][1] = o++;
jad[r][0] = par;
ll t;
for(ll j = 1 ; j < 20 ; j++){
if(jad[r][j - 1] == -1){
t = j;
break;
}
jad[r][j] = jad[jad[r][j - 1]][j - 1];
lb[r][j][0] = o;
adj[o].push_back(lb[r][j - 1][0]); jda[lb[r][j - 1][0]].push_back(o);
adj[o].push_back(lb[jad[r][j - 1]][j - 1][0]); jda[lb[jad[r][j - 1]][j - 1][0]].push_back(o);
o++;
lb[r][j][1] = o;
adj[lb[r][j - 1][1]].push_back(o); jda[o].push_back(lb[r][j - 1][1]);
adj[lb[jad[r][j - 1]][j - 1][1]].push_back(o); jda[o].push_back(lb[jad[r][j - 1]][j - 1][1]);
o++;
}
for(ll j = t ; j < 20 ; j++){
lb[r][j][0] = lb[r][t - 1][0];
lb[r][j][1] = lb[r][t - 1][1];
}
for(auto i : tdj[r]){
if(i == par) continue;
lDFS(i , r);
}
dep--;
return;
}
ll find_jad(ll v , ll d){
d = dis[v] - d;
for(ll j = 0 ; j < 20 ; j++){
if(d & (1 << j)){
v = jad[v][j];
}
}
return v;
}
ll lca(ll v , ll u){
if(dis[v] > dis[u]) swap(v , u);
u = find_jad(u , dis[v]);
if(v == u) return v;
for(ll j = 19 ; ~j ; j--){
if(jad[v][j] != jad[u][j]){
v = jad[v][j];
u = jad[u][j];
}
}
return jad[v][0];
}
void fDFS(ll r){
mark[r] = true;
for(auto i : adj[r]){
if(mark[i]) continue;
fDFS(i);
}
f.push_back(r);
return;
}
void cDFS(ll r){
c[r] = k;
for(auto i : jda[r]){
if(c[i] != -1) continue;
cDFS(i);
}
return;
}
void solve(){
ll n , m;
cin>>n;
for(ll i = 0 ; i < 40 * n ; i++){
adj[i].clear(); jda[i].clear();
}
for(ll i = 0 ; i < n ; i++){
tdj[i].clear();
for(ll j = 0 ; j < 20 ; j++) jad[i][j] = -1;
}
for(ll i = 1 ; i < n ; i++){
ll v , u;
cin>>v>>u; v--; u--;
tdj[v].push_back(u); tdj[u].push_back(v);
}
cin>>m; o = m;
for(ll i = 0 ; i < m ; i++){
cin>>a[i]>>b[i]; a[i]--; b[i]--;
}
lDFS(0 , -1);
for(ll i = 0 ; i < m ; i++){
ll l = lca(a[i] , b[i]);
ll v = a[i];
for(ll j = 19 ; ~j ; j--){
ll u = jad[v][j];
if(u == -1) continue;
if(dis[u] < dis[l] - 1) continue;
jda[i].push_back(lb[v][j][1]); adj[lb[v][j][1]].push_back(i);
v = u;
}
v = jad[a[i]][0];
for(ll j = 19 ; ~j ; j--){
ll u = jad[v][j];
if(u == -1) continue;
if(dis[u] < dis[l] - 1) continue;
adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].push_back(i);
v = u;
}
v = b[i];
for(ll j = 19 ; ~j ; j--){
ll u = jad[v][j];
if(u == -1) continue;
if(dis[u] < dis[l] - 1) continue;
jda[i].push_back(lb[v][j][1]); adj[lb[v][j][1]].push_back(i);
v = u;
}
v = jad[b[i]][0];
for(ll j = 19 ; ~j ; j--){
ll u = jad[v][j];
if(u == -1) continue;
if(dis[u] < dis[l] - 1) continue;
adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].push_back(i);
v = u;
}
v = lb[b[i]][0][0];
adj[v].push_back(i); jda[i].push_back(v);
v = lb[a[i]][0][1];
jda[v].push_back(i); adj[i].push_back(v);
}
f.clear();
for(ll i = 0 ; i < o ; i++){
c[i] = -1;
mark[i] = false;
}
k = 0;
for(ll i = 0 ; i < o ; i++){
if(mark[i]) continue;
fDFS(i);
}
reverse(all(f));
for(auto i : f){
if(c[i] != -1) continue;
cDFS(i);
k++;
}
for(ll i = 0 ; i < m ; i++){
if(!mark[c[i]]){
cout<<"No\n";
return;
}
mark[c[i]] = false;
}
cout<<"Yes\n";
return;
}
/*
3
4
1 2
2 3
3 4
2
1 4
3 2
4
1 2
2 3
3 4
2
1 3
2 4
4
1 2
2 3
3 4
2
3 1
4 3
*/
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll T;
cin>>T;
while(T--) solve();
return 0;
}
Compilation message
jail.cpp: In function 'void lDFS(ll, ll)':
jail.cpp:48:25: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
48 | lb[r][j][0] = lb[r][t - 1][0];
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
237900 KB |
Output is correct |
| 2 |
Correct |
109 ms |
238056 KB |
Output is correct |
| 3 |
Incorrect |
111 ms |
237996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
237976 KB |
Output is correct |
| 2 |
Incorrect |
108 ms |
237896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
237976 KB |
Output is correct |
| 2 |
Incorrect |
108 ms |
237896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
237976 KB |
Output is correct |
| 2 |
Incorrect |
108 ms |
237896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
237976 KB |
Output is correct |
| 2 |
Incorrect |
108 ms |
237896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
238008 KB |
Output is correct |
| 2 |
Correct |
108 ms |
237900 KB |
Output is correct |
| 3 |
Correct |
108 ms |
237976 KB |
Output is correct |
| 4 |
Incorrect |
108 ms |
237896 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
237900 KB |
Output is correct |
| 2 |
Correct |
109 ms |
238056 KB |
Output is correct |
| 3 |
Incorrect |
111 ms |
237996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
