| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 547999 |
2022-04-12T08:06:52 Z |
fcmalkcin |
Jail (JOI22_jail) |
C++17 |
|
34 ms |
43536 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)
const ll maxn=5e5+100;
const ll base=300;
const ll mod= 1e9+7 ;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
/// have medal in APIO
/// goal 2/8
struct tk
{
ll pos;
ll pos1;
tk ()
{
pos=-1;
pos1=-1;
}
};
ll id1[maxn];
tk st[4*maxn];
tk mer(tk a,tk b)
{
a.pos=max(a.pos,b.pos);
a.pos1=max(a.pos1,b.pos1);
return a;
}
tk get(ll id,ll l,ll r,ll x,ll y)
{
tk c;
if (x>r||y<l)
return c;
if (x<=l&&y>=r)
return st[id];
ll mid=(l+r)/2;
return mer(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
}
void update(ll id,ll l,ll r,ll x,ll diff)
{
if (x>r||x<l)
return ;
if (l==r)
{
tk c;
st[id]=c;
if (diff==0)
st[id].pos=id1[l];
else if (diff==1)
st[id].pos1=id1[l];
return ;
}
ll mid=(l+r)/2;
update(id*2,l,mid,x,diff);
update(id*2+1,mid+1,r,x,diff);
st[id]=mer(st[id*2],st[id*2+1]);
}
ll pos[maxn];
ll c=1;
ll cnt=0;
ll nc[maxn];
ll nch[maxn];
ll anc[maxn][20];
ll dep[maxn];
vector<ll> adj[maxn];
ll siz[maxn];
ll nxt[maxn];
ll pre[maxn];
ll n;
ll col[maxn];
ll lca(ll x,ll y)
{
if (dep[x]<dep[y])
swap(x,y);
ll kc=dep[x]-dep[y];
for (int i=19; i>=0; i--)
if (kc&(1ll<<i))
x=anc[x][i];
if (x==y)
return x;
for (int i=19; i>=0; i--)
if (anc[x][i]!=anc[y][i])
x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
void dfs(ll u,ll par)
{
siz[u]=1;
anc[u][0]=par;
for (int i=1; i<=19; i++)
anc[u][i]=anc[anc[u][i-1]][i-1];
for (auto to:adj[u])
{
if (to==par)
continue;
dep[to]=dep[u]+1;
dfs(to,u);
siz[u]+=siz[to];
}
}
void hld(ll u,ll par)
{
cnt++;
id1[cnt]=u;
pos[u]=cnt;
nc[u]=c;
if (!nch[nc[u]])
nch[nc[u]]=u;
pll mx=make_pair(0,0);
for (auto to:adj[u])
{
if (to==par)
continue;
mx=max(mx,make_pair(siz[to],to));
}
if (mx.ss)
hld(mx.ss,u);
for (auto to:adj[u])
{
if (to==par||to==mx.ss)
continue;
c++;
hld(to,u);
}
}
bool chkall;
ll getnear(ll u,ll x)
{
if (dep[u]<dep[x])
swap(u,x);
ll kc=dep[u]-dep[x]-1;
for (int i=19; i>=0; i--)
if (kc&(1ll<<i))
u=anc[u][i];
return u;
}
tk get1(ll x,ll u)
{
tk a;
while (1)
{
if (nc[x]==nc[u])
{
a=mer(a,get(1,1,n,pos[u],pos[x]));
break;
}
else
{
ll h=nch[nc[x]];
a=mer(a,get(1,1,n,pos[h],pos[x]));
x=anc[h][0];
}
}
return a;
}
void dfs1(ll u)
{
col[u]=1;
ll h=nxt[u];
update(1,1,n,pos[h],1);
ll l=lca(u,h);
vector<pll> vt;
if (h==l)
{
vt.pb(make_pair(u,getnear(u,l)));
}
else
{
vt.pb(make_pair(u,l));
vt.pb(make_pair(anc[h][0],l));
}
while (1)
{
tk nw;
for (auto p:vt)
nw=mer(nw,get1(p.ff,p.ss));
if (nw.pos1!=-1)
{
/* cout <<u<<" wtf"<<endl;
cout <<nw.pos1<<" "<<nw.pos<<" wtf"<<endl;
for (auto to:vt)
{
cout <<to.ff<<" "<<to.ss<<endl;
}*/
chkall=false;
return ;
}
else if (nw.pos!=-1)
{
dfs1(pre[nw.pos]);
}
else
break;
}
update(1,1,n,pos[h],2);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
ll t;
cin>> t;
while (t--)
{
chkall=true;
cin>> n;
for (int i=1; i<=n-1; i++)
{
ll x, y;
cin>>x>> y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(1,0);
c=1;
cnt=0;
hld(1,0);
ll m;
cin>> m;
for (int i=1; i<=m; i++)
{
ll x, y;
cin>>x>> y;
nxt[x]=y;
pre[y]=x;
}
for (int i=1; i<=n; i++)
{
if (pre[i])
{
ll h=pos[i];
//cout <<i<<" "<<h<<" chk1"<<endl;
update(1,1,n,h,0);
}
}
for (int i=1; i<=n; i++)
{
if (nxt[i]&&!col[i])
{
// cout <<i<<" "<<col[i]<<" chkdfs"<<endl;
dfs1(i);
}
}
if (chkall) cout <<"Yes"<<endl;
else cout <<"No"<<endl;
for (int i=1; i<=n; i++)
{
adj[i].clear();
nxt[i]=0;
pre[i]=0;
col[i]=0;
}
for (int i=1; i<=4*n; i++)
{
tk c;
st[i]=c;
}
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:215:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
215 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jail.cpp:216:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
43464 KB |
Output is correct |
| 2 |
Correct |
22 ms |
43452 KB |
Output is correct |
| 3 |
Correct |
23 ms |
43348 KB |
Output is correct |
| 4 |
Incorrect |
34 ms |
43476 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
43408 KB |
Output is correct |
| 2 |
Correct |
22 ms |
43468 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
43484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
43408 KB |
Output is correct |
| 2 |
Correct |
22 ms |
43468 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
43484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
43408 KB |
Output is correct |
| 2 |
Correct |
22 ms |
43468 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
43484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
43408 KB |
Output is correct |
| 2 |
Correct |
22 ms |
43468 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
43484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
43432 KB |
Output is correct |
| 2 |
Correct |
21 ms |
43412 KB |
Output is correct |
| 3 |
Correct |
21 ms |
43516 KB |
Output is correct |
| 4 |
Correct |
27 ms |
43424 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
43536 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
43464 KB |
Output is correct |
| 2 |
Correct |
22 ms |
43452 KB |
Output is correct |
| 3 |
Correct |
23 ms |
43348 KB |
Output is correct |
| 4 |
Incorrect |
34 ms |
43476 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
