| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1033918 |
2024-07-25T07:45:13 Z |
vjudge1 |
Jail (JOI22_jail) |
C++17 |
|
580 ms |
627592 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];
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();
}
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);
// 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';
}
}
// 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();
}
/*
1
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
*/
/*
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:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | 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:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid=l+r>>1;
| ~^~
jail.cpp: In function 'int32_t main()':
jail.cpp:193:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
193 | freopen("jail.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jail.cpp:194:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | freopen("jail.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
580 ms |
627532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
627592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
627592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
627592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
627592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
552 ms |
627464 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
580 ms |
627532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
