| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 879567 |
2023-11-27T16:25:48 Z |
vivkostov |
Jail (JOI22_jail) |
C++14 |
|
279 ms |
520436 KB |
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int q,n,m,c,d,a[2000005],b[2000005],child[2000005],machild[2000005],used[2000005],up[2000005],bin[2000005][60],level[2000005],usedl[2000005],in,brr,brj;
vector<int>v[2000005],p[20000005];
void find_child(int beg,int par,int lev)
{
level[beg]=lev;
child[beg]++;
bin[beg][0]=par;
int w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!child[w])
{
find_child(w,beg,lev+1);
child[beg]+=child[w];
machild[beg]=max(machild[beg],child[w]);
}
}
}
void heavylight(int beg,int last)
{
in++;
up[beg]=last;
used[beg]=in;
int w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!used[w]&&child[w]==machild[beg])
{
heavylight(w,last);
break;
}
}
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(!used[w])heavylight(w,w);
}
}
void make_start(int l,int r,int h)
{
if(l==r)return;
int mid=(l+r)/2;
p[h+n].push_back(h*2+n);
p[h+n].push_back(h*2+1+n);
make_start(l,mid,h*2);
make_start(mid+1,r,h*2+1);
}
void make_finish(int l,int r,int h)
{
if(l==r)return;
int mid=(l+r)/2;
p[h*2+n*5].push_back(h+n*5);
p[h*2+1+n*5].push_back(h+n*5);
make_finish(l,mid,h*2);
make_finish(mid+1,r,h*2+1);
}
void update(int l,int r,int ql,int qr,int h,int to,int type)
{
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr)
{
if(type==1)p[h+n].push_back(to);
if(type==2)p[to].push_back(h+n*5);
if(type==3)p[to].push_back(h+n);
if(type==4)p[h+n*5].push_back(to);
return;
}
int mid=(l+r)/2;
update(l,mid,ql,qr,h*2,to,type);
update(mid+1,r,ql,qr,h*2+1,to,type);
}
void make_bin()
{
for(int j=1;j<=30;j++)
{
for(int i=1;i<=n;i++)
{
bin[i][j]=bin[bin[i][j-1]][j-1];
}
}
}
void add_all()
{
for(int i=1;i<=m;i++)
{
update(1,n,used[a[i]],used[a[i]],1,i,1);
update(1,n,used[b[i]],used[b[i]],1,i,2);
}
}
int lca(int x,int y)
{
if(level[x]>level[y])swap(x,y);
for(int i=30;i>=0;i--)
{
if(level[bin[y][i]]>=level[x])y=bin[y][i];
}
if(x==y)return x;
for(int i=30;i>=0;i--)
{
if(bin[x][i]!=bin[y][i])
{
x=bin[x][i];
y=bin[y][i];
}
}
return bin[x][0];
}
void go_up_heavy(int beg,int lc,int prisoner)
{
if(level[up[beg]]==level[lc])
{
update(1,n,used[up[beg]],used[beg],1,prisoner,3);
update(1,n,used[up[beg]],used[beg],1,prisoner,4);
return;
}
if(level[up[beg]]>level[lc])
{
update(1,n,used[up[beg]],used[beg],1,prisoner,3);
update(1,n,used[up[beg]],used[beg],1,prisoner,4);
go_up_heavy(bin[up[beg]][0],lc,prisoner);
return;
}
update(1,n,used[lc],used[beg],1,prisoner,3);
update(1,n,used[lc],used[beg],1,prisoner,4);
}
void add_path()
{
for(int i=1;i<=m;i++)
{
int g=lca(a[i],b[i]);
go_up_heavy(a[i],g,i);
go_up_heavy(b[i],g,i);
}
}
int tin[2000005],low[2000005],tim,lamp,comp[2000005],co;
stack<int>s;
void conect(int beg,int par)
{
tim++;
tin[beg]=tim;
low[beg]=tim;
s.push(beg);
int w;
for(int i=0;i<p[beg].size();i++)
{
w=p[beg][i];
if(tin[w]==-1)continue;
if(!tin[w])
{
conect(w,beg);
low[beg]=min(low[beg],low[w]);
}
if(par!=w)low[beg]=min(low[beg],low[w]);
}
if(low[beg]==tin[beg])
{
co++;
while(s.top()!=beg)
{
//cout<<s.top()<<" ";
tin[s.top()]=-1;
comp[s.top()]=co;
s.pop();
}
//cout<<s.top()<<" ";
tin[s.top()]=-1;
comp[s.top()]=co;
s.pop();
//cout<<endl;
}
}
void resh()
{
find_child(1,0,1);
heavylight(1,1);
make_start(1,n,1);
make_finish(1,n,1);
add_all();
make_bin();
add_path();
/*for(int i=1;i<=55;i++)
{
cout<<i<<" | ";
for(int j=0;j<p[i].size();j++)
{
cout<<p[i][j]<<" ";
}
cout<<endl;
}
*/
for(int i=1;i<=m;i++)
{
if(!tin[i])conect(i,0);
//cout<<endl;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
if(comp[i]==comp[j]&&i!=j)
{
lamp=1;
cout<<"No"<<endl;
break;
}
}
if(lamp)break;
}
if(!lamp)cout<<"Yes"<<endl;
for(int i=0;i<=n*10;i++)
{
a[i]=0;
b[i]=0;
child[i]=0;
machild[i]=0;
used[i]=0;
up[i]=0;
level[i]=0;
tin[i]=0;
low[i]=0;
v[i].clear();
for(int j=0;j<=30;j++)bin[i][j]=0;
}
for(int i=0;i<=10*n;i++)p[i].clear();
in=0;
brr=0;
brj=0;
tim=0;
lamp=0;
}
void read()
{
cin>>q;
for(int z=1;z<=q;z++)
{
cin>>n;
for(int i=1;i<n;i++)
{
cin>>c>>d;
v[c].push_back(d);
v[d].push_back(c);
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i];
}
resh();
}
}
int main()
{
speed();
read();
return 0;
}
Compilation message
jail.cpp: In function 'void find_child(int, int, int)':
jail.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
jail.cpp: In function 'void heavylight(int, int)':
jail.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
jail.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
jail.cpp: In function 'void conect(int, int)':
jail.cpp:155:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(int i=0;i<p[beg].size();i++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
519508 KB |
Output is correct |
| 2 |
Correct |
279 ms |
519704 KB |
Output is correct |
| 3 |
Correct |
220 ms |
519504 KB |
Output is correct |
| 4 |
Incorrect |
205 ms |
520276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
519512 KB |
Output is correct |
| 2 |
Correct |
185 ms |
519652 KB |
Output is correct |
| 3 |
Correct |
192 ms |
520372 KB |
Output is correct |
| 4 |
Incorrect |
185 ms |
520436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
519512 KB |
Output is correct |
| 2 |
Correct |
185 ms |
519652 KB |
Output is correct |
| 3 |
Correct |
192 ms |
520372 KB |
Output is correct |
| 4 |
Incorrect |
185 ms |
520436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
519512 KB |
Output is correct |
| 2 |
Correct |
185 ms |
519652 KB |
Output is correct |
| 3 |
Correct |
192 ms |
520372 KB |
Output is correct |
| 4 |
Incorrect |
185 ms |
520436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
519512 KB |
Output is correct |
| 2 |
Correct |
185 ms |
519652 KB |
Output is correct |
| 3 |
Correct |
192 ms |
520372 KB |
Output is correct |
| 4 |
Incorrect |
185 ms |
520436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
184 ms |
519704 KB |
Output is correct |
| 2 |
Correct |
179 ms |
519584 KB |
Output is correct |
| 3 |
Correct |
179 ms |
519504 KB |
Output is correct |
| 4 |
Correct |
179 ms |
519508 KB |
Output is correct |
| 5 |
Incorrect |
196 ms |
519760 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
519508 KB |
Output is correct |
| 2 |
Correct |
279 ms |
519704 KB |
Output is correct |
| 3 |
Correct |
220 ms |
519504 KB |
Output is correct |
| 4 |
Incorrect |
205 ms |
520276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
