| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 877788 |
2023-11-23T14:33:18 Z |
simona1230 |
Jail (JOI22_jail) |
C++17 |
|
25 ms |
104456 KB |
#include <bits/stdc++.h>
#define endl "\n"
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target(avx2)
using namespace std;
const int maxver=1e6;
const int maxn=9*120000;
int q,n,m;
vector<int> f[maxn];
void read()
{
cin>>n;
for(int i=1; i<=n; i++)
f[i].clear();
for(int i=1; i<n; i++)
{
int x,y;
cin>>x>>y;
f[x].push_back(y);
f[y].push_back(x);
}
cin>>m;
}
int num;
int ts[maxn];
int te[maxn];
int dw[maxn];
int up[maxn];
vector<int> v[maxver],o[maxver];
void add_edge(int x,int y)
{
v[x].push_back(y);
o[y].push_back(x);
}
void make_tree(int i,int l,int r)
{
if(l==r)
{
ts[i]=num++;
te[i]=num++;
//cout<<ts[i]<<" "<<te[i]<<" "<<l<<" "<<r<<endl;
dw[l]=ts[i];
up[l]=te[i];
return;
}
ts[i]=num++;
te[i]=num++;
//cout<<ts[i]<<" "<<te[i]<<" "<<l<<" "<<r<<endl;
int mid=(l+r)/2;
make_tree(i*2,l,mid);
make_tree(i*2+1,mid+1,r);
add_edge(ts[i],ts[i*2]);
add_edge(ts[i],ts[i*2+1]);
add_edge(te[i*2],te[i]);
add_edge(te[i*2+1],te[i]);
}
int used[maxn];
int sz[maxn];
void size_(int i)
{
used[i]=1;
sz[i]=1;
for(int j=0; j<f[i].size(); j++)
{
int nb=f[i][j];
if(!used[nb])
{
size_(nb);
sz[i]+=sz[nb];
}
}
}
int jump[maxn][21];
int pos[maxn];
int chain[maxn];
int lvl[maxn];
int cnt=1;
void hld(int i,int lead,int level,int par)
{
pos[i]=cnt++;
chain[i]=lead;
lvl[i]=level;
int maxx=0,big=0;
for(int j=0; j<f[i].size(); j++)
{
int nb=f[i][j];
if(sz[nb]>maxx&&nb!=par)
{
maxx=sz[nb];
big=nb;
}
}
if(big)
{
//cout<<"here "<<i<<" "<<lead<<" "<<ver<<endl;
hld(big,lead,level+1,i);
jump[big][0]=i;
}
for(int j=0; j<f[i].size(); j++)
{
int nb=f[i][j];
if(nb!=big&&nb!=par)
{
hld(nb,nb,level+1,i);
jump[nb][0]=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];
}
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);
x=make_jump(x,abs(lvl[x]-lvl[y]));
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||r<ql||l>qr)return;
if(ql<=l&&r<=qr)
{
add_edge(pr,ts[i]);
add_edge(te[i],pr);
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<=m; i++)
{
int x,y;
cin>>x>>y;
add_edge(dw[pos[x]],i);
add_edge(i,up[pos[y]]);
int st,lca_=lca(x,y);
//cout<<lca_<<endl;
st=x;
while(true)
{
int ed=chain[st];
if(lvl[ed]<lvl[lca_])ed=lca_;
update(1,1,n,pos[ed],pos[st],i);
//cout<<pos[ed]<<" "<<pos[st]<<endl;
if(ed==lca_)break;
st=jump[ed][0];
}
st=y;
while(true)
{
int ed=chain[st];
if(lvl[ed]<lvl[lca_])ed=lca_;
update(1,1,n,pos[ed],pos[st],i);
//cout<<pos[ed]<<" "<<pos[st]<<endl;
if(ed==lca_)break;
st=jump[ed][0];
}
}
}
int comp;
stack<int> topo;
int used1[maxn];
int used2[maxn];
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);
}
topo.push(i);
}
void dfs2(int i)
{
used2[i]=comp;
for(int j=0; j<o[i].size(); j++)
{
int nb=o[i][j];
if(!used2[nb])
dfs2(nb);
}
}
bool usedf[maxn];
void check()
{
///mp.clear();
for(int i=1; i<=m; i++)
if(!used1[i])dfs1(i);
comp=0;
while(topo.size())
{
int ver=topo.top();
topo.pop();
if(!used2[ver])
{
comp++;
dfs2(ver);
}
}
//cout<<comp<<" "<<num<<endl;
bool ans=1;
for(int i=1;i<=m;i++)
{
if(usedf[i] == true) ans = false;
usedf[i] = true;
}
if(ans)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--)
{
read();
for(int i=1; i<= num; i++)
{
v[i].clear();
o[i].clear();
}
for(int i=1;i<maxn;i++)
{
/**used[i]=pos[i]=used1[i]=0;
used2[i]=chain[i]=ts[i]=0;
te[i]=sz[i]=dw[i]=up[i]=lvl[i]=0;*/
used[i] = 0;
used1[i] = 0;
used2[i] = 0;
usedf[i] = 0;
}
/*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));*/
/**for(int i=1; i<=n; i++)
for(int j=0; j<=20; j++)
jump[i][j]=0;*/
size_(1);
cnt=1;
hld(1,1,1,-1);
prec();
num=m+1;
make_tree(1,1,n);
make_graph();
/*for(int i=1;i<num;i++)
{
cout<<i<<": ";
for(int j=0;j<v[i].size();j++)
{
cout<<v[i][j]<<" ";
}
cout<<endl;
}*/
check();
}
return 0;
}
/*
1
6
2 4
4 1
1 5
5 3
3 6
2
2 3
6 1
*/
Compilation message
jail.cpp:5:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
5 | #pragma GCC target(avx2)
| ^~~~
jail.cpp: In function 'void size_(int)':
jail.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void hld(int, int, int, int)':
jail.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int j=0; j<f[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:218:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | for(int j=0; j<v[i].size(); j++)
| ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(int)':
jail.cpp:230:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
230 | for(int j=0; j<o[i].size(); j++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
104284 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
104456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
104428 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
104284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
104428 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
104284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
104428 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
104284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
104428 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
104284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
104284 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
104284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
104284 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
104456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
