| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 877289 |
2023-11-23T05:45:27 Z |
simona1230 |
Jail (JOI22_jail) |
C++17 |
|
2124 ms |
1048576 KB |
#include <bits/stdc++.h>
using namespace std;
long long q,n,m;
vector<long long> f[1000001];
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[1000001];// number of the vertex corresponding
long long te[1000001];// to the given tree and segment of the hld
long long dw[1000001];
long long up[1000001];
vector<long long> v[1000001],o[1000001];
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[1000001];
long long jump[1000001][21];
long long sz[1000001];
long long pos[1000001];// new number of vertex i in original graph
long long chain[1000001];// leader of the chain in which i is
long long maxx[1000001];
long long lvl[1000001];
void necessities(long long i,long long h)
{
lvl[i]=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)
{
pos[i]=cnt++;
chain[pos[i]]=pos[lead];
if(maxx[i])
{
hld(maxx[i],lead);
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);
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(long long i=1; i<=m; i++)
{
long long x,y;
cin>>x>>y;
//cout<<i<<" "<<dw[pos[x]]<<" "<<up[pos[y]]<<endl;
v[dw[pos[x]]].push_back(i);
o[i].push_back(dw[pos[x]]);
v[i].push_back(up[pos[y]]);
o[up[pos[y]]].push_back(i);
long long ver=pos[lca(x,y)];
long long c1=pos[x];
while(1)
{
long long c2=chain[c1];
if(lvl[c2]<lvl[ver])c2=ver;
update(1,1,n,c2,c1,i);
c1=c2;
if(c2==ver)break;
c1=jump[c1][0];
}
c1=pos[y];
while(1)
{
long long c2=chain[c1];
if(lvl[c2]<lvl[ver])c2=ver;
update(1,1,n,c2,c1,i);
c1=c2;
if(c2==ver)break;
c1=jump[c1][0];
}
}
}
long long used1[1000001];
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[1000001];
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);
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;
}
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)':
jail.cpp:91: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]
91 | for(long long j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:194: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]
194 | for(long long j=0; j<v[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(long long int)':
jail.cpp:208: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]
208 | for(long long j=0; j<o[i].size(); j++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
121952 KB |
Output is correct |
| 2 |
Correct |
25 ms |
121948 KB |
Output is correct |
| 3 |
Correct |
21 ms |
121948 KB |
Output is correct |
| 4 |
Correct |
986 ms |
122500 KB |
Output is correct |
| 5 |
Correct |
2048 ms |
122008 KB |
Output is correct |
| 6 |
Correct |
62 ms |
122028 KB |
Output is correct |
| 7 |
Correct |
64 ms |
122028 KB |
Output is correct |
| 8 |
Correct |
66 ms |
121948 KB |
Output is correct |
| 9 |
Correct |
119 ms |
128592 KB |
Output is correct |
| 10 |
Correct |
153 ms |
188804 KB |
Output is correct |
| 11 |
Correct |
2104 ms |
122220 KB |
Output is correct |
| 12 |
Correct |
2124 ms |
122520 KB |
Output is correct |
| 13 |
Correct |
273 ms |
210428 KB |
Output is correct |
| 14 |
Correct |
275 ms |
211028 KB |
Output is correct |
| 15 |
Correct |
665 ms |
231492 KB |
Output is correct |
| 16 |
Correct |
1265 ms |
297776 KB |
Output is correct |
| 17 |
Correct |
350 ms |
241200 KB |
Output is correct |
| 18 |
Correct |
269 ms |
219724 KB |
Output is correct |
| 19 |
Correct |
350 ms |
233852 KB |
Output is correct |
| 20 |
Correct |
333 ms |
233812 KB |
Output is correct |
| 21 |
Correct |
389 ms |
238408 KB |
Output is correct |
| 22 |
Correct |
204 ms |
200912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
121948 KB |
Output is correct |
| 2 |
Correct |
22 ms |
121944 KB |
Output is correct |
| 3 |
Correct |
62 ms |
121944 KB |
Output is correct |
| 4 |
Runtime error |
532 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
121948 KB |
Output is correct |
| 2 |
Correct |
22 ms |
121944 KB |
Output is correct |
| 3 |
Correct |
62 ms |
121944 KB |
Output is correct |
| 4 |
Runtime error |
532 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
121948 KB |
Output is correct |
| 2 |
Correct |
22 ms |
121944 KB |
Output is correct |
| 3 |
Correct |
62 ms |
121944 KB |
Output is correct |
| 4 |
Runtime error |
532 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
121948 KB |
Output is correct |
| 2 |
Correct |
22 ms |
121944 KB |
Output is correct |
| 3 |
Correct |
62 ms |
121944 KB |
Output is correct |
| 4 |
Runtime error |
532 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
121948 KB |
Output is correct |
| 2 |
Runtime error |
493 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
121952 KB |
Output is correct |
| 2 |
Correct |
25 ms |
121948 KB |
Output is correct |
| 3 |
Correct |
21 ms |
121948 KB |
Output is correct |
| 4 |
Correct |
986 ms |
122500 KB |
Output is correct |
| 5 |
Correct |
2048 ms |
122008 KB |
Output is correct |
| 6 |
Correct |
62 ms |
122028 KB |
Output is correct |
| 7 |
Correct |
64 ms |
122028 KB |
Output is correct |
| 8 |
Correct |
66 ms |
121948 KB |
Output is correct |
| 9 |
Correct |
119 ms |
128592 KB |
Output is correct |
| 10 |
Correct |
153 ms |
188804 KB |
Output is correct |
| 11 |
Correct |
2104 ms |
122220 KB |
Output is correct |
| 12 |
Correct |
2124 ms |
122520 KB |
Output is correct |
| 13 |
Correct |
273 ms |
210428 KB |
Output is correct |
| 14 |
Correct |
275 ms |
211028 KB |
Output is correct |
| 15 |
Correct |
665 ms |
231492 KB |
Output is correct |
| 16 |
Correct |
1265 ms |
297776 KB |
Output is correct |
| 17 |
Correct |
350 ms |
241200 KB |
Output is correct |
| 18 |
Correct |
269 ms |
219724 KB |
Output is correct |
| 19 |
Correct |
350 ms |
233852 KB |
Output is correct |
| 20 |
Correct |
333 ms |
233812 KB |
Output is correct |
| 21 |
Correct |
389 ms |
238408 KB |
Output is correct |
| 22 |
Correct |
204 ms |
200912 KB |
Output is correct |
| 23 |
Correct |
22 ms |
121948 KB |
Output is correct |
| 24 |
Correct |
22 ms |
121944 KB |
Output is correct |
| 25 |
Correct |
62 ms |
121944 KB |
Output is correct |
| 26 |
Runtime error |
532 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Halted |
0 ms |
0 KB |
- |
