| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1034121 |
2024-07-25T09:54:19 Z |
vjudge1 |
Jail (JOI22_jail) |
C++17 |
|
10 ms |
14776 KB |
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
const int maxn=12e4+23;
int n,m;
int pos[maxn];
vector<int> ke[maxn],adj[maxn*4];
int Count,deg[maxn*4];
int heavy[maxn],par[maxn][21],in[maxn],out[maxn],dep[maxn],Time,head[maxn],rev[maxn];
vector<pii> el;
int dd[maxn*4];
void lca(int u,int v)
{
while (u!=v)
{
if (u<v) swap(u,v);
u/=2;
}
while(u!=1)
{
dd[u]++;
// cerr<< u<<'\n';
u/=2;
}
dd[u]++;
}
void reset()
{
for1(i,0,n+1)
{
ke[i].clear();
}
for1(i,0,max(n*4+1,Count+1))
{
deg[i]=0;
adj[i].clear();
dd[i]=0;
}
Time=0;
Count=0;
}
void Build(int id=1,int l=1,int r=n)
{
// cerr<<"skrt "<< id<<' '<<l<<' '<<r<<'\n';
Count++;
if (l==r)
{
pos[rev[l]]=id;
return;
}
int mid=l+r>>1;
Build(id*2,l,mid);
Build(id*2+1,mid+1,r);
adj[id].pb(id*2);
adj[id].pb(id*2+1);
// cerr<< id<<" -> "<<id*2<<'\n';
// cerr<< id<<" -> "<<id*2+1<<'\n';
deg[id*2]++;
deg[id*2+1]++;
}
void Add(int node,int u,int v,int id=1,int l=1,int r=n)
{
if (u>r || v<l) return;
if (u<=l && r<=v)
{
// adj[node].pb(id);
el.pb({node,id});
// cerr<< node<<" -> "<<id<<'\n';
deg[id]++;
return;
}
int mid=l+r>>1;
Add(node,u,v,id*2,l,mid);
Add(node,u,v,id*2+1,mid+1,r);
}
int predfs(int u=1, int pre=1)
{
int sz=1;
int sz_mx=1;
for(int v:ke[u])
{
if (v==pre) continue;
dep[v]=dep[u]+1;
int sz_v=predfs(v,u);
if (sz_v >= sz_mx) heavy[u]=v;
sz+=sz_v;
}
return sz;
}
void hld(int u=1,int pre=1,int hd=1)
{
// cerr<< u<<" s\n";
in[u]=++Time;
rev[Time]=u;
head[u]=hd;
par[u][0]=pre;
for1(i,1,20) par[u][i]=par[par[u][i-1]][i-1];
if (heavy[u]!=-1) hld(heavy[u],u,hd);
for(int v:ke[u])
{
if (v==pre || v==heavy[u]) continue;
hld(v,u,v);
}
out[u]=Time;
}
bool is_ancestor(int u,int v) {return in[u]<=in[v] && out[v]<=out[u];}
int jump(int u,int v)
{
for2(i,20,0) if (!is_ancestor(par[v][i],u)) v=par[v][i];
return v;
}
void Update_hld(int node, int u, int v)
{
// cerr<< " ru\n";
while (head[u]!=head[v])
{
if (dep[head[u]]<dep[head[v]]) swap(u,v);
Add(node, in[head[u]], in[u]);
// cerr<< node<<' '<<head[u]<<' '<<u<<" ok\n";
u=par[head[u]][0];
}
if (dep[u]> dep[v]) swap(u,v);
// cerr<<node<<' '<<u<<' '<<v<< " ok\n";
Add(node,in[u],in[v]);
}
void sol()
{
cin >> n;
reset();
for1(i,1,n-1)
{
int u,v;cin >>u>>v;
ke[u].pb(v);
ke[v].pb(u);
}
for1(i,1,n) heavy[i]=-1;
predfs();
// cerr<< "mf\n";
// cerr<< heavy[1]<<" q wd\n";
hld();
Build();
cin >> m;
for1(i,1,m)
{
int s,t;cin >> s>> t;
if (is_ancestor(s,t))
{
int ss=jump(s,t);
// cerr<<ss<< " sir?\n";
Update_hld(pos[s],ss,t);
}
else
{
Update_hld(pos[s],par[s][0],t);
// cerr<<"zz "<< par[s][0]<<' '<<t<<'\n';
}
}
// cerr<< el.size()<<'\n';
for(auto [u,v]: el)
{
// int uu;
// if (is_ancestor(u,v)) uu=jump(u,v);
// else uu=par[u][0];
lca(u,v);
// cerr<< u<<' '<<v<<" gg\n";
}
for(auto [u,v]: el)
{
if (dd[v])
{
cout << "No\n";
return;
}
adj[u].pb(v);
}
// for1(i,1,n)
// {
// cerr<<"zzz "<< i<<' '<<in[i]<<' '<<head[i]<<'\n';
// }
// cerr<< Count<<'\n';
vector<int> L;
if (deg[1]!=0)
{
cout << "No\n";
return;
}
L.pb(1);
int g=0;
while (!L.empty())
{
int u=L.back();
// cerr<<"wa "<< u<<' '<<deg[u]<<'\n';
L.pop_back();
g++;
for(int v:adj[u])
{
--deg[v];
if (deg[v]==0) L.pb(v);
// if (u==1) cerr<<"as "<< v<<'\n';
}
}
if (Count!=g) cout << "No\n";
else cout << "Yes\n";
// for1(i,1,Count) cout<<"za " << i<<' '<<deg[i]<<'\n';
// cerr<< g<<'\n';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("jail.inp","r",stdin);
// freopen("jail.out","w",stdout);
int t=1;cin >> t;
while (t--) sol();
}
/*
2
3
1 2
1 3
2
1 1
1 2
7
1 2
1 3
3 4
4 5
3 6
6 7
2
3 4
5 6
*/
/*
2
18
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
5
17 5
12 1
10 15
11 17
6 14
20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
1
20 8
*/
Compilation message
jail.cpp: In function 'void Build(long long int, long long int, long long int)':
jail.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid=l+r>>1;
| ~^~
jail.cpp: In function 'void Add(long long int, long long int, long long int, long long int, long long int, long long int)':
jail.cpp:84:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14428 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14616 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
14776 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14616 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
14776 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14616 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
14776 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14616 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
14776 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14576 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 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 |
9 ms |
14428 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
