| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1076617 |
2024-08-26T15:01:39 Z |
modwwe |
Jail (JOI22_jail) |
C++17 |
|
6 ms |
26968 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;
main()
{
#ifndef ONLINE_JUDGE
// fin(task),fou(task);
#endif
NHP
/// cin>>s1;
modwwe
phongbeo(),down
//checktime
}
int st[17][120001];
int depth[120001];
int head[120001];
int pos[120001];
vector<int> v[120001];
int heavy[120001];
ib a[120001];
int b[120001];
int c[120001];
stack<int> s;
int vitri[120001];
vector<int> v2[480001];
int f[120001];
int dfs(int x,int y)
{
int sz=1;
int mxz=0;
st[0][x]=y;
depth[x]=depth[y]+1;
for(auto f:v[x])
{
if(f!=y)
{
s2=dfs(f,x);
sz+=s2;
if(s2>mxz)
heavy[x]=f,mxz=s2;
}
}
return sz;
}
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:v[x])
if(pos[f]==0)
des(f,f);
}
struct IT
{
int t[480000];
int t2[480000];
void ff(int x)
{
for(int i=x*2; i<=x*2+1; i++)
t2[i]+=t2[x];
t2[x]=0;
}
void upd_in(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return;
if(l>=l1&&r<=r1)
{
t[node]=1;
return;
}
int mid=l+r>>1;
upd_in(node<<1,l,mid,l1,r1);
upd_in(node<<1|1,mid+1,r,l1,r1);
t[node]=t[node<<1]+t[node<<1|1];
}
int get(int node,int l,int r,int l1,int r1,int x)
{
if(l>r1||r<l1) return 0;
if(l>=l1&&r<=r1)
{
v2[node].pb(x);
t2[node]++;
// cout<<t2[node]<<" "<<node<<" "<<l<<" "<<r<<" "<<l1<<" "<<r1,down
return t[node];
}
int mid=l+r>>1;
return get(node<<1,l,mid,l1,r1,x)+get(node<<1|1,mid+1,r,l1,r1,x);
}
int get2(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return 0;
if(l>=l1&&r<=r1) return t2[node];
ff(node);
int mid=l+r>>1;
return get2(node<<1,l,mid,l1,r1)+get2(node<<1|1,mid+1,r,l1,r1);
}
void setup(int node,int l,int r)
{
t[node]=0;
if(l==r)
{
t2[node]--;
if(t2[node]<=0)t2[node]=inf;
f[l]=node;
return;
}
ff(node);
int mid=l+r>>1;
setup(node<<1,l,mid);
setup(node<<1|1,mid+1,r);
t2[node]=min(t2[node<<1],t2[node<<1|1]);
}
void ff2(int x)
{
for(int i=x*2; i<=x*2+1; i++)
t[i]+=t[x],
t2[i]-=t[x];
t[x]=0;
}
void upd_out2(int node,int l,int r)
{
if(t2[node]!=0)return;
if(l==r)
{
t2[node]=inf;
c[vitri[l]]=0;
if(b[vitri[l]]==0) s.push(vitri[l]);
return;
}
ff2(node);
int mid=l+r>>1;
upd_out2(node<<1,l,mid);
upd_out2(node<<1|1,mid+1,r);
t2[node]=min(t2[node<<1],t2[node<<1|1]);
}
void upd_out(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return;
if(l>=l1&&r<=r1)
{
t2[node]--;
t[node]++;
if(t2[node]==0)ff2(node),upd_out2(node,l,r);
return;
}
ff2(node);
int mid=l+r>>1;
upd_out(node<<1,l,mid,l1,r1);
upd_out(node<<1|1,mid+1,r,l1,r1);
t2[node]=min(t2[node<<1],t2[node<<1|1]);
}
int get_hld(int x,int y,int z)
{
if(pos[head[x]]<=pos[y]) return get(1,1,n,pos[y],pos[x],z);
return get(1,1,n,pos[head[x]],pos[x],z)+get_hld(st[0][head[x]],y,z);
}
int get_namgiua(int x,int y,int z)
{
if(depth[x]>depth[y]) swap(x,y);
s2=lca(x,y);
s3=lca2(y,s2);
return get_hld(x,s2,z)+get_hld(y,s3,z);
}
void ou(int x,int y)
{
if(pos[head[x]]<=pos[y]) upd_out(1,1,n,pos[y],pos[x]);
else upd_out(1,1,n,pos[head[x]],pos[x]),ou(st[0][head[x]],y);
}
void upd_out_out(int x,int y)
{
if(depth[x]>depth[y]) swap(x,y);
s2=lca(x,y);
s3=lca2(y,s2);
ou(x,s2);
ou(y,s3);
}
void upd_out_in(int x)
{
x=f[pos[x]];
while(x!=0)
{
for(auto f:v2[x])
{
b[f]--;
if(b[f]==1&&c[f]==0)s.push(f);
}
x/=2;
}
}
} stt;
void out(int x)
{
stt.upd_out_out(a[x].a,a[x].b);
stt.upd_out_in(a[x].a);
}
void phongbeo()
{
cin>>n;
/// cach 1
dem=0;
for(int i=1; i<=n; i++)
v[i].clear(),b[i]=0,c[i]=0,f[i]=0,heavy[i]=0,pos[i]=0,head[i]=0,depth[i]=0,vitri[i]=0;
for(int i=1; i<=n*4; i++)
v2[i].clear(),stt.t[i]=0,stt.t2[i]=0;
for(int i=1; i<n; i++)
cin>>l>>r,v[l].pb(r),v[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]];
cin>>m;
for(int i=1; i<=m; i++)
cin>>a[i].a>>a[i].b,stt.upd_in(1,1,n,pos[a[i].a],pos[a[i].a]);
// cout<<1;
for(int i=1; i<=m; i++)
b[i]=stt.get_namgiua(a[i].a,a[i].b,i);
for(int i=1; i<=m; i++)
{
c[i]=stt.get2(1,1,n,pos[a[i].b],pos[a[i].b])-1;
vitri[pos[a[i].b]]=i;
if(b[i]==1&&c[i]==0)
{
s.push(i);
}
}
b[0]=inf;
stt.setup(1,1,n);
dem4=0;
while(!s.empty())
{
int x=s.top();
s.pop();
out(x);
dem4++;
}
if(dem4!=m) cout<<"NO";
else cout<<"YES";
}
/**
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
*/
Compilation message
jail.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main()
| ^~~~
jail.cpp: In member function 'void IT::upd_in(int, int, int, int, int)':
jail.cpp:148:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
148 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'int IT::get(int, int, int, int, int, int)':
jail.cpp:163:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
163 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'int IT::get2(int, int, int, int, int)':
jail.cpp:171:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
171 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'void IT::setup(int, int, int)':
jail.cpp:186:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
186 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'void IT::upd_out2(int, int, int)':
jail.cpp:209:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
209 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'void IT::upd_out(int, int, int, int, int)':
jail.cpp:225:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
225 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
25056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
20828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
20828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
20828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
20828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
26968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
25056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
