| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1077515 |
2024-08-27T07:47:57 Z |
BABY_GANGSTER |
Jail (JOI22_jail) |
C++14 |
|
21 ms |
25948 KB |
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void phongbeo();
const int inf=1e9;
const int mod2=1e9+7;
const int mod1=998244353;
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c,d,e;
};
int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid;
int i,s10,s12;
int kk;
int el=29;
#define getchar_unlocked getchar
inline int scan(){
char c = getchar_unlocked();
int x = 0;
while(c<'0'||c>'9'){
c=getchar_unlocked();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+c-'0';
c=getchar_unlocked();
}
return x;
}
main()
{
#ifndef ONLINE_JUDGE
//fin(task),fou(task);
#endif
NHP
/// cin>>s1;
int xx=scan();
// modwwe
while(xx--)
phongbeo(),down
//checktime
}
int st[17][120007];
int depth[120007];
int head[120007];
int pos[120007];
vector<int> v2[120007];
vector<ib> v[480007][2];
int heavy[120007];
ib a[120007];
int f[120007];
int sz[120007];
int mxz[120007];
int c[480007][2];
void dfs(int x,int y)
{
sz[x]=1;
mxz[x]=0;
st[0][x]=y;
depth[x]=depth[y]+1;
for(auto f:v2[x])
{
if(f!=y)
{
dfs(f,x);
sz[x]+=sz[f];
if(sz[f]>sz[x])
heavy[x]=f,mxz[x]=sz[f];
}
}
}
int lca2(int x,int y)
{
if(depth[x]<depth[y]) swap(x,y);
int ss=depth[x]-depth[y]-1;
if(ss>=0)
for(int j=0; j<17; ++j)
if(bit(ss,j))
x=st[j][x];
if(st[0][x]==y) return x;
if(ss!=-1) x=st[0][x];
for(int j=16; j>=0; --j)
if(st[j][x]!=st[j][y])
x=st[j][x],y=st[j][y];
return x;
}
int lca(int x,int y)
{
if(depth[x]<depth[y]) swap(x,y);
int ss=depth[x]-depth[y];
for(int j=0; j<17; ++j)
if(bit(ss,j))
x=st[j][x];
if(x==y) return x;
for(int j=16; j>=0; --j)
if(st[j][x]!=st[j][y])
x=st[j][x],y=st[j][y];
return st[0][x];
}
void des(int x,int y)
{
head[x]=y;
pos[x]=++dem;
if(heavy[x]!=0)
des(heavy[x],y);
for(auto f:v2[x])
if(pos[f]==0)
des(f,f);
}
struct IT
{
void setup(int node,int l,int r)
{
// cout<<node<<" "<<l<<" "<<r,debug
if(node!=1)v[node>>1][0].pb({node,0});
if(node!=1) v[node][1].pb({node>>1,1});
if(l==r)
{
f[l]=node;
return;
}
int mid=l+r>>1;
setup(node<<1,l,mid);
setup(node<<1|1,mid+1,r);
}
void upd(int node,int l,int r,int l1,int r1,int x)
{
if(l>r1||r<l1) return;
if(l>=l1&&r<=r1)
{
v[x][0].pb({node,0});
// if(x==5) cout<<node,debug
return;
}
int mid=l+r>>1;
upd(node<<1,l,mid,l1,r1,x);
upd(node<<1|1,mid+1,r,l1,r1,x);
}
void upd2(int node,int l,int r,int l1,int r1,int x)
{
if(l>r1||r<l1) return;
if(l>=l1&&r<=r1)
{
v[node][1].pb({x,0});
///if(node==5) cout<<x<<" "<<l1<<" "<<r1<<" fadfdafafa",debug
return;
}
int mid=l+r>>1;
upd2(node<<1,l,mid,l1,r1,x);
upd2(node<<1|1,mid+1,r,l1,r1,x);
}
void hld(int x,int y,int z)
{
if(pos[x]<pos[y]) return;
if(pos[head[x]]<=pos[y]) upd(1,1,n,pos[y],pos[x],z);
else upd(1,1,n,pos[head[x]],pos[x],z),hld(st[0][head[x]],y,z);
}
void hld2(int x,int y,int z)
{
if(pos[x]<pos[y]) return;
if(pos[head[x]]<=pos[y]) upd2(1,1,n,pos[y],pos[x],z);
else upd2(1,1,n,pos[head[x]],pos[x],z),hld2(st[0][head[x]],y,z);
}
void upd_hld(int x,int y)
{
s2=lca(x,y);
if(s2!=y)s3=lca2(s2,y);
hld(st[0][x],s2,f[pos[x]]);
if(s2!=y) hld(y,s3,f[pos[x]]);
if(s2==y)s2=lca2(x,s2);
hld2(x,s2,f[pos[x]]);
if(s2!=y) hld2(st[0][y],s3,f[pos[x]]);
}
} stt;
bool de;
void dfs2(int x,int y)
{
c[x][y]=1;
for(auto f:v[x][y]){
if(f.b==0&&c[f.a][0]==1){de=1; return;}
if(c[f.a][f.b]) continue;
dfs2(f.a,f.b);
if(de)return;
}
c[x][y]=2;
}
void phongbeo()
{
n=scan();
/// cach 1
de=0;
dem=0;
for(int i=1; i<=n; i++)
v2[i].clear(),f[i]=0,heavy[i]=0,pos[i]=0,head[i]=0,depth[i]=0;
for(int i=1; i<=n*4; i++)
v[i][0].clear(),v[i][1].clear(),c[i][0]=c[i][1]=0;
for(int i=1; i<n; i++)
l=scan(),r=scan(),v2[l].pb(r),v2[r].pb(l);
dfs(1,0);
des(1,0);
for(int i=1; i<17; i++)
for(int j=1; j<=n; j++)
st[i][j]=st[i-1][st[i-1][j]];
stt.setup(1,1,n);
m=scan();
for(int i=1; i<=m; i++)
a[i].a=scan(),a[i].b=scan(),stt.upd_hld(a[i].a,a[i].b),v[f[pos[a[i].a]]][0].pb({f[pos[a[i].b]],1});
if(n>=120000) assert(0);
dem=0;
for(int i=1; i<=m; i++)
{
if(!c[f[pos[a[i].a]]][0]) dfs2(f[pos[a[i].a]],0);
if(de)break;
}
if(de) cout<<"No";
else cout<<"Yes";
}
Compilation message
jail.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
63 | main()
| ^~~~
jail.cpp: In member function 'void IT::setup(int, int, int)':
jail.cpp:156:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
156 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'void IT::upd(int, int, int, int, int, int)':
jail.cpp:169:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
169 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'void IT::upd2(int, int, int, int, int, int)':
jail.cpp:183:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
183 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'void IT::upd_hld(int, int)':
jail.cpp:205:1: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
205 | if(s2==y)s2=lca2(x,s2);
| ^~
jail.cpp:206:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
206 | hld2(x,s2,f[pos[x]]);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
25944 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
25824 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25708 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
25944 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25708 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
25944 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25708 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
25944 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25708 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
25944 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
25944 KB |
Output is correct |
| 2 |
Correct |
20 ms |
25944 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
25828 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
25944 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
25824 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
