| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 877311 |
2023-11-23T06:14:45 Z |
simona1230 |
Jail (JOI22_jail) |
C++17 |
|
5000 ms |
1048576 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn=4*1e6;
long long q,n,m;
vector<long long> f[maxn];
void read()
{
cin>>n;
for(long long i=1; i<=n; i++)
f[i].clear();
for(long long i=1; i<n; i++)
{
long long x,y;
cin>>x>>y;
f[x].push_back(y);
f[y].push_back(x);
}
}
long long num;
long long ts[maxn];// number of the vertex corresponding
long long te[maxn];// to the given tree and segment of the hld
long long dw[maxn];
long long up[maxn];
vector<long long> v[maxn],o[maxn];
void make_tree(long long i,long long l,long long r)
{
if(l==r)
{
ts[i]=num++;
dw[l]=ts[i];
te[i]=num++;
up[l]=te[i];
//cout<<l<<" "<<r<<" "<<te[i]<<endl;
return;
}
long long mid=(l+r)/2;
ts[i]=num++;
te[i]=num++;
//cout<<l<<" "<<r<<" "<<te[i]<<endl;
make_tree(i*2,l,mid);
make_tree(i*2+1,mid+1,r);
long long il=ts[i*2];
long long ir=ts[i*2+1];
v[ts[i]].push_back(il);
v[ts[i]].push_back(ir);
o[il].push_back(ts[i]);
o[ir].push_back(ts[i]);
il=te[i*2];
ir=te[i*2+1];
v[il].push_back(te[i]);
v[ir].push_back(te[i]);
o[te[i]].push_back(il);
o[te[i]].push_back(ir);
}
long long used[maxn];
long long jump[1000001][21];
long long sz[maxn];
long long pos[maxn];// new number of vertex i in original graph
long long chain[maxn];// leader of the chain in which i is
long long maxx[maxn];
long long lvl[maxn];
void necessities(long long i,long long h)
{
sz[i]=1;
used[i]=1;
for(long long j=0; j<f[i].size(); j++)
{
long long nb=f[i][j];
if(!used[nb])
{
necessities(nb,h+1);
sz[i]+=sz[nb];
if(sz[maxx[i]]<sz[nb])maxx[i]=nb;
}
}
}
long long cnt=1;
void hld(long long i,long long lead,int h)
{
pos[i]=cnt++;
chain[pos[i]]=pos[lead];
lvl[pos[i]]=h;
if(maxx[i])
{
hld(maxx[i],lead,h+1);
jump[pos[maxx[i]]][0]=pos[i];
}
for(long long j=0; j<f[i].size(); j++)
{
long long nb=f[i][j];
if(pos[nb]==0)
{
hld(nb,nb,h+1);
jump[pos[nb]][0]=pos[i];
}
}
}
void prec()
{
for(long long j=1; j<=20; j++)
{
for(long long i=1; i<=n; i++)
{
jump[i][j]=jump[jump[i][j-1]][j-1];
//cout<<i<<" "<<j<<" "<<jump[i][j]<<endl;
}
}
}
long long make_jump(long long x,long long k)
{
for(long long i=20; i>=0; i--)
if(k&(1<<i))
x=jump[x][i];
return x;
}
long long lca(long long x,long long y)
{
if(lvl[x]>lvl[y])swap(x,y);
y=make_jump(y,abs(lvl[y]-lvl[x]));
//cout<<x<<" "<<y<<endl;
if(x==y)return x;
for(long long i=20; i>=0; i--)
{
if(jump[x][i]!=jump[y][i])
{
x=jump[x][i];
y=jump[y][i];
}
}
return jump[x][0];
}
void update(long long i,long long l,long long r,long long ql,long long qr,long long pr)
{
if(ql>qr)return;
if(ql<=l&&r<=qr)
{
//cout<<l<<"-"<<r<<endl;
long long idx=ts[i];
//cout<<idx<<endl;
v[pr].push_back(idx);
o[idx].push_back(pr);
idx=te[i];
//cout<<idx<<endl;
v[idx].push_back(pr);
o[pr].push_back(idx);
return;
}
long long mid=(l+r)/2;
update(i*2,l,mid,ql,min(mid,qr),pr);
update(i*2+1,mid+1,r,max(ql,mid+1),qr,pr);
}
void make_graph()
{
/*for(int i=1;i<=n;i++)
cout<<chain[i]<<" ";
cout<<endl;*/
for(long long i=1; i<=m; i++)
{
long long x,y;
cin>>x>>y;
x=pos[x];
y=pos[y];
//cout<<i<<" "<<dw[pos[x]]<<" "<<up[pos[y]]<<endl;
v[dw[x]].push_back(i);
o[i].push_back(dw[x]);
v[i].push_back(up[y]);
o[up[y]].push_back(i);
long long ver=lca(x,y);
//cout<<ver<<endl;
long long c1=x;
while(1)
{
long long c2=chain[c1];
if(lvl[c2]<lvl[ver])c2=ver;
update(1,1,n,c2,c1,i);
//cout<<c2<<" "<<c1<<endl;
if(c2==ver)break;
c1=jump[c2][0];
}
c1=y;
while(1)
{
long long c2=chain[c1];
if(lvl[c2]<lvl[ver])c2=ver;
update(1,1,n,c2,c1,i);
//cout<<c2<<" "<<c1<<endl;
if(c2==ver)break;
c1=jump[c2][0];
}
}
}
long long used1[maxn];
stack<long long> st;
void dfs1(long long i)
{
used1[i]=1;
for(long long j=0; j<v[i].size(); j++)
{
long long nb=v[i][j];
if(!used1[nb])
{
dfs1(nb);
}
}
st.push(i);
}
long long used2[maxn];
void dfs2(long long i)
{
used2[i]=1;
for(long long j=0; j<o[i].size(); j++)
{
long long nb=o[i][j];
if(!used2[nb])
{
dfs2(nb);
}
}
}
void check()
{
memset(used1,0,sizeof(used1));
memset(used2,0,sizeof(used2));
for(long long i=1;i<=m;i++)
{
if(!used1[i])dfs1(i);
}
long long cnt=0;
while(st.size())
{
long long vr=st.top();
st.pop();
if(vr<=m&&!used2[vr])
{
cnt++;
dfs2(vr);
}
}
if(cnt==m)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>q;
while(q--)
{
for(long long i=1; i<=num; i++)
{
o[i].clear();
v[i].clear();
}
memset(maxx,0,sizeof(maxx));
memset(used,0,sizeof(used));
read();
cnt=1;
necessities(1,1);
hld(1,1,1);
prec();
cin>>m;
num=m+1;
make_tree(1,1,n);
make_graph();
/*for(long long i=1;i<num;i++)
{
cout<<i<<": ";
for(long long j=0;j<v[i].size();j++)
cout<<v[i][j]<<" ";
cout<<endl;
}*/
check();
}
return 0;
}
/*
1
8
1 7
1 8
8 3
3 2
7 6
7 5
5 4
*/
Compilation message
jail.cpp: In function 'void necessities(long long int, long long int)':
jail.cpp:70:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(long long j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void hld(long long int, long long int, int)':
jail.cpp:92:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(long long j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:201:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for(long long j=0; j<v[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(long long int)':
jail.cpp:215:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for(long long j=0; j<o[i].size(); j++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
411080 KB |
Output is correct |
| 2 |
Correct |
96 ms |
426236 KB |
Output is correct |
| 3 |
Correct |
84 ms |
426064 KB |
Output is correct |
| 4 |
Correct |
4213 ms |
426876 KB |
Output is correct |
| 5 |
Execution timed out |
5048 ms |
426764 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
426076 KB |
Output is correct |
| 2 |
Correct |
77 ms |
426252 KB |
Output is correct |
| 3 |
Correct |
236 ms |
426320 KB |
Output is correct |
| 4 |
Correct |
238 ms |
426380 KB |
Output is correct |
| 5 |
Runtime error |
417 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
426076 KB |
Output is correct |
| 2 |
Correct |
77 ms |
426252 KB |
Output is correct |
| 3 |
Correct |
236 ms |
426320 KB |
Output is correct |
| 4 |
Correct |
238 ms |
426380 KB |
Output is correct |
| 5 |
Runtime error |
417 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
426076 KB |
Output is correct |
| 2 |
Correct |
77 ms |
426252 KB |
Output is correct |
| 3 |
Correct |
236 ms |
426320 KB |
Output is correct |
| 4 |
Correct |
238 ms |
426380 KB |
Output is correct |
| 5 |
Runtime error |
417 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
426076 KB |
Output is correct |
| 2 |
Correct |
77 ms |
426252 KB |
Output is correct |
| 3 |
Correct |
236 ms |
426320 KB |
Output is correct |
| 4 |
Correct |
238 ms |
426380 KB |
Output is correct |
| 5 |
Runtime error |
417 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
426068 KB |
Output is correct |
| 2 |
Correct |
87 ms |
426296 KB |
Output is correct |
| 3 |
Correct |
95 ms |
426288 KB |
Output is correct |
| 4 |
Correct |
78 ms |
426076 KB |
Output is correct |
| 5 |
Execution timed out |
5005 ms |
426336 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
411080 KB |
Output is correct |
| 2 |
Correct |
96 ms |
426236 KB |
Output is correct |
| 3 |
Correct |
84 ms |
426064 KB |
Output is correct |
| 4 |
Correct |
4213 ms |
426876 KB |
Output is correct |
| 5 |
Execution timed out |
5048 ms |
426764 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
