| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 927348 |
2024-02-14T18:43:13 Z |
andrei_boaca |
Jail (JOI22_jail) |
C++17 |
|
19 ms |
33884 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int t,n,m,A[120005],B[120005],in[120005],out[120005],timp,par[120005],niv[1200005],dp[21][120005],nr[120005];
bool isheavy[120005];
vector<int> muchii[120005];
vector<vector<int>> v;
vector<set<pii>> suf,active;
set<pii> vtm;
vector<vector<set<int>>> arb;
vector<int> tati;
vector<set<int>> emp;
int where[120005],poz[120005];
vector<int> stiva;
bool use[120005];
bool isancestor(int a,int b)
{
return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
if(niv[a]>niv[b])
swap(a,b);
if(isancestor(a,b))
return a;
for(int i=18;i>=0;i--)
if(dp[i][a]!=0&&!isancestor(dp[i][a],b))
a=dp[i][a];
return par[a];
}
int dist(int a,int b)
{
int lca=LCA(a,b);
return niv[a]+niv[b]-2*niv[lca];
}
void initdfs(int nod)
{
nr[nod]=1;
timp++;
in[nod]=timp;
dp[0][nod]=par[nod];
for(int i=1;i<=18;i++)
dp[i][nod]=dp[i-1][dp[i-1][nod]];
int who=0,maxim=0;
for(int i:muchii[nod])
if(i!=par[nod])
{
par[i]=nod;
niv[i]=niv[nod]+1;
initdfs(i);
nr[nod]+=nr[i];
if(nr[i]>maxim)
{
maxim=nr[i];
who=i;
}
}
if(who!=0)
isheavy[who]=1;
out[nod]=timp;
}
void buildhld()
{
for(int i=1;i<=n;i++)
{
bool ok=1;
for(int j:muchii[i])
if(j!=par[i]&&isheavy[j])
{
ok=0;
break;
}
if(ok)
{
vector<int> nodes;
int nod=i;
while(true)
{
nodes.push_back(nod);
if(!isheavy[nod])
break;
nod=par[nod];
}
for(int i=0;i<nodes.size();i++)
{
where[nodes[i]]=v.size();
poz[nodes[i]]=i;
}
v.push_back(nodes);
arb.push_back(emp);
suf.push_back(vtm);
active.push_back(vtm);
int lg=arb.size();
lg--;
arb[lg].resize(4*(int)nodes.size()+5);
}
}
}
void addnode(int nod,int ind,int add)
{
int chain=where[nod];
int p=poz[nod];
if(add==1)
active[chain].insert({p,ind});
else
active[chain].erase({p,ind});
}
void update(int chain,int nod,int st,int dr,int a,int b,int val,int add)
{
if(st>=a&&dr<=b)
{
if(add==1)
arb[chain][nod].insert(val);
else
arb[chain][nod].erase(val);
return;
}
int mij=(st+dr)/2;
if(a<=mij)
update(chain,nod*2,st,mij,a,b,val,add);
if(b>mij)
update(chain,nod*2+1,mij+1,dr,a,b,val,add);
}
void query(int chain,int nod,int st,int dr,int p)
{
tati.push_back(nod);
if(st==dr)
return;
int mij=(st+dr)/2;
if(p<=mij)
query(chain,nod*2,st,mij,p);
if(p>mij)
query(chain,nod*2+1,mij+1,dr,p);
}
void addseg(int a,int b,int ind,int add)
{
int lca=LCA(a,b);
while(niv[a]>=niv[lca])
{
int p=poz[a];
int chain=where[a];
int last=v[chain].size();
last--;
if(where[a]==where[lca])
last=poz[lca];
if(p<=last)
{
if(last!=(int)v[chain].size()-1)
update(chain,1,0,(int)v[chain].size()-1,p,last,ind,add);
else
{
pii x={p,ind};
if(add==1)
suf[chain].insert(x);
else
suf[chain].erase(x);
}
}
a=par[v[chain][last]];
}
while(niv[b]>niv[lca])
{
int p=poz[b];
int chain=where[b];
int last=v[chain].size();
last--;
if(where[b]==where[lca])
last=poz[lca]-1;
if(p<=last)
{
if(last!=(int)v[chain].size()-1)
update(chain,1,0,(int)v[chain].size()-1,p,last,ind,add);
else
{
pii x={p,ind};
if(add==1)
suf[chain].insert(x);
else
suf[chain].erase(x);
}
}
b=par[v[chain][last]];
}
}
void dfs1(int nod)
{
use[nod]=1;
addseg(A[nod],B[nod],nod,-1);
addnode(B[nod],nod,-1);
int chain=where[A[nod]];
int p=poz[A[nod]];
while(!suf[chain].empty())
{
auto it=suf[chain].upper_bound({p,1e9});
if(it==suf[chain].begin())
break;
it=prev(it);
int x=(*it).second;
dfs1(x);
}
tati.clear();
query(chain,1,0,v[chain].size()-1,p);
for(int x:tati)
{
while(!arb[chain][x].empty())
{
int y=*arb[chain][x].begin();
dfs1(y);
}
}
int a=A[nod];
int b=B[nod];
int lca=LCA(a,b);
while(a!=0&&niv[a]>=niv[lca])
{
p=poz[a];
chain=where[a];
int last=v[chain].size();
last--;
if(where[a]==where[lca])
last=poz[lca];
while(!active[chain].empty())
{
auto it=active[chain].lower_bound({p,0});
if(it==active[chain].end())
break;
if((*it).first>last)
break;
int x=(*it).second;
dfs1(x);
}
a=par[v[chain][last]];
}
while(b!=0&&niv[b]>niv[lca])
{
p=poz[b];
chain=where[b];
int last=v[chain].size();
last--;
if(where[a]==where[lca])
last=poz[lca]-1;
while(!active[chain].empty())
{
auto it=active[chain].lower_bound({p,0});
if(it==active[chain].end())
break;
if((*it).first>last)
break;
int x=(*it).second;
dfs1(x);
}
b=par[v[chain][last]];
}
stiva.push_back(nod);
}
void dfs2(int nod)
{
use[nod]=1;
addseg(A[nod],B[nod],nod,-1);
addnode(A[nod],nod,-1);
int chain=where[B[nod]];
int p=poz[B[nod]];
while(!suf[chain].empty())
{
auto it=suf[chain].upper_bound({p,1e9});
if(it==suf[chain].begin())
break;
it=prev(it);
int x=(*it).second;
dfs2(x);
}
tati.clear();
query(chain,1,0,v[chain].size()-1,p);
for(int x:tati)
{
while(!arb[chain][x].empty())
{
int y=*arb[chain][x].begin();
dfs2(y);
}
}
int a=A[nod];
int b=B[nod];
int lca=LCA(a,b);
while(a!=0&&niv[a]>=niv[lca])
{
p=poz[a];
chain=where[a];
int last=v[chain].size();
last--;
if(where[a]==where[lca])
last=poz[lca];
while(!active[chain].empty())
{
auto it=active[chain].lower_bound({p,0});
if(it==active[chain].end())
break;
if((*it).first>last)
break;
int x=(*it).second;
dfs2(x);
}
a=par[v[chain][last]];
}
while(b!=0&&niv[b]>niv[lca])
{
p=poz[b];
chain=where[b];
int last=v[chain].size();
last--;
if(where[a]==where[lca])
last=poz[lca]-1;
while(!active[chain].empty())
{
auto it=active[chain].lower_bound({p,0});
if(it==active[chain].end())
break;
if((*it).first>last)
break;
int x=(*it).second;
dfs2(x);
}
b=par[v[chain][last]];
}
}
void solve()
{
cin>>n;
timp=0;
v.clear();
suf.clear();
active.clear();
arb.clear();
arb.shrink_to_fit();
for(int i=1;i<=n;i++)
{
muchii[i].clear();
isheavy[i]=0;
}
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
niv[1]=1;
initdfs(1);
cin>>m;
for(int i=1;i<=m;i++)
cin>>A[i]>>B[i];
buildhld();
stiva.clear();
for(int i=1;i<=m;i++)
{
addseg(A[i],B[i],i,+1);
addnode(B[i],i,+1);
}
for(int i=1;i<=m;i++)
if(!use[i])
dfs1(i);
for(int i=0;i<v.size();i++)
assert(suf[i].empty());
reverse(stiva.begin(),stiva.end());
for(int i=1;i<=m;i++)
{
use[i]=0;
addseg(A[i],B[i],i,+1);
addnode(A[i],i,+1);
}
int nrcomp=0;
for(int i:stiva)
if(!use[i])
{
nrcomp++;
dfs2(i);
}
if(nrcomp==m)
cout<<"Yes\n";
else
cout<<"No\n";
/*for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
if(i!=j)
{
if(onchain(A[j],A[i],B[i]))
{
edges[j].push_back(i);
grad[i]++;
}
if(onchain(B[j],A[i],B[i]))
{
edges[i].push_back(j);
grad[j]++;
}
}*/
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while(t--)
solve();
return 0;
}
Compilation message
jail.cpp: In function 'void buildhld()':
jail.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<nodes.size();i++)
| ~^~~~~~~~~~~~~
jail.cpp: In function 'void solve()':
jail.cpp:364:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
364 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 4 |
Runtime error |
17 ms |
33884 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
33884 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
33884 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
33884 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 3 |
Runtime error |
16 ms |
33884 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
2 ms |
16876 KB |
Output is correct |
| 4 |
Correct |
3 ms |
16728 KB |
Output is correct |
| 5 |
Runtime error |
19 ms |
33784 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 4 |
Runtime error |
17 ms |
33884 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
