| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 877535 |
2023-11-23T09:47:31 Z |
simona1230 |
Jail (JOI22_jail) |
C++17 |
|
667 ms |
1048576 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int q,n,m;
vector<int> f[200001];
bool test=0;
void read()
{
cin>>n;
for(int i=1; i<n; i++)
{
int x,y;
cin>>x>>y;
f[x].push_back(y);
f[y].push_back(x);
}
}
int num;
int ts[800001];// number of the vertex corresponding
int te[800001];// to the given tree and segment of the hld
int dw[200001];
int up[200001];
vector<int> v[maxn],o[maxn];
void make_tree(int i,int l,int 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;
}
int 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);
int il=ts[i*2];
int 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);
}
int used[200001];
int jump[200001][21];
int sz[200001];
int pos[200001];// new number of vertex i in original graph
int chain[200001];// leader of the chain in which i is
int maxx[200001];
int lvl[200001];
void necessities(int i,int h)
{
sz[i]=1;
used[i]=1;
for(int j=0; j<f[i].size(); j++)
{
int nb=f[i][j];
if(!used[nb])
{
necessities(nb,h+1);
sz[i]+=sz[nb];
if(sz[maxx[i]]<sz[nb])maxx[i]=nb;
}
}
}
int cnt=1;
void hld(int i,int lead,int h)
{
pos[i]=cnt++;
chain[pos[i]]=pos[lead];
lvl[pos[i]]=h;
int val=0,vr=0;
for(int j=0;j<f[i].size();j++)
{
int nb=f[i][j];
if(sz[nb]>val)
{
val=sz[nb];
vr=nb;
}
}
hld(vr,lead,h+1);
for(int j=0; j<f[i].size(); j++)
{
int nb=f[i][j];
if(nb!=vr&&pos[nb]==0)
{
hld(nb,nb,h+1);
jump[pos[nb]][0]=pos[i];
}
}
}
void prec()
{
for(int j=1; j<=20; j++)
{
for(int i=1; i<=n; i++)
{
jump[i][j]=jump[jump[i][j-1]][j-1];
//cout<<i<<" "<<j<<" "<<jump[i][j]<<endl;
}
}
}
int make_jump(int x,int k)
{
for(int i=20; i>=0; i--)
if(k&(1<<i))
x=jump[x][i];
return x;
}
int lca(int x,int 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(int 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(int i,int l,int r,int ql,int qr,int pr)
{
if(ql>qr)return;
if(r<ql||l>qr)return;
if(ql<=l&&r<=qr)
{
//cout<<l<<"-"<<r<<endl;
int 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;
}
int mid=(l+r)/2;
update(i*2,l,mid,ql,qr,pr);
update(i*2+1,mid+1,r,ql,qr,pr);
}
void make_graph()
{
/*for(int i=1;i<=n;i++)
cout<<chain[i]<<" ";
cout<<endl;*/
for(int i=1; i<=m; i++)
{
int 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);
int ver=lca(x,y);
//cout<<ver<<endl;
int c1=x;
int br = 0;
while(1)
{
int 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];
br++;
//if(br >= n + 1) assert(false);
}
c1=y;
br = 0;
while(1)
{
int 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];
br++;
//if(br >= n + 1) assert(false);
}
}
}
int used1[maxn];
stack<int> st;
void dfs1(int i)
{
used1[i]=1;
for(int j=0; j<v[i].size(); j++)
{
int nb=v[i][j];
if(!used1[nb])
{
dfs1(nb);
}
}
st.push(i);
}
int used2[maxn];
void dfs2(int i)
{
used2[i]=1;
for(int j=0; j<o[i].size(); j++)
{
int nb=o[i][j];
if(!used2[nb])
{
dfs2(nb);
}
}
}
void check()
{
for(int i=1;i<=m;i++)
{
if(!used1[i])dfs1(i);
}
int cnt1=0;
while(st.size())
{
int vr=st.top();
st.pop();
if(vr<=m&&!used2[vr])
{
cnt1++;
dfs2(vr);
}
}
if(cnt1==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--)
{
test=0;
for(int i=1; i<maxn; i++)
{
o[i].clear();
v[i].clear();
}
memset(maxx,0,sizeof(maxx));
memset(used,0,sizeof(used));
memset(pos,0,sizeof(pos));
memset(used1,0,sizeof(used1));
memset(used2,0,sizeof(used2));
memset(chain,0,sizeof(chain));
memset(ts,0,sizeof(ts));
memset(te,0,sizeof(te));
memset(sz,0,sizeof(sz));
memset(dw,0,sizeof(dw));
memset(up,0,sizeof(up));
memset(lvl,0,sizeof(lvl));
read();
for(int i=1;i<=n;i++)
for(int j=0;j<=20;j++)
jump[i][j]=0;
for(int i=1; i<=n; i++)
f[i].clear();
cnt=1;
necessities(1,1);
hld(1,1,1);
prec();
cin>>m;
num=m+1;
make_tree(1,1,n);
make_graph();
check();
}
return 0;
}
Compilation message
jail.cpp: In function 'void necessities(int, int)':
jail.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void hld(int, int, int)':
jail.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j=0;j<f[i].size();j++)
| ~^~~~~~~~~~~~
jail.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:222:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | for(int j=0; j<v[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(int)':
jail.cpp:236:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
236 | for(int j=0; j<o[i].size(); j++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
667 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
578 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
578 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
578 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
578 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
538 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
667 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
