| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1006879 |
2024-06-24T09:30:23 Z |
modwwe |
Jail (JOI22_jail) |
C++17 |
|
4 ms |
6492 KB |
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#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".out","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void phongbeo();
const int mod2=1e9+7;
const int mod1=998244353;
struct icd
{
int a,b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a,b;
long long c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c, d,e,f;
};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
fin(task),fou(task);
#endif
NHP;
/// cin>>s1;
modwwe
phongbeo(),down
}
int st[17][120007];
int depth[120007];
int head[120007];
int pos[120007];
vector<int> v[120007];
ic a[50001];
int d[50001];
int heavy[120007];
bool b[50001];
int sz[100007];
void dfs(int x,int y)
{
sz[x]=1;
int mxz=0;
st[0][x]=y;
depth[x]=depth[y]+1;
for(auto f:v[x])
{
if(f!=y)
{
dfs(f,x);
sz[x]+=sz[f];
if(sz[f]>mxz)
heavy[x]=f,mxz=sz[f];
}
}
}
int lca(int x,int y)
{
if(depth[x]<depth[y]) swap(x,y);
int ss=depth[x]-depth[y];
if(ss!=0)
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 IT1
{
int t[480001];
void build(int node,int l,int r)
{
t[node]=0;
if(l==r) return;
int mid=l+r>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
}
void ff(int x)
{
for(int i=x*2; i<=x*2+1; i++)
t[i]+=t[x];
t[x]=0;
}
void upd(int node,int l,int r,int l1,int r1,int c)
{
if(l>r1||r<l1) return;
if(l>=l1&&r<=r1)
{
t[node]+=c;
return;
}
ff(node);
int mid=l+r>>1;
upd(node<<1,l,mid,l1,r1,c);
upd(node<<1|1,mid+1,r,l1,r1,c);
}
int get(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return 0;
if(l>=l1&&r<=r1) return t[node];
ff(node);
int mid=l+r>>1;
return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1);
}
} st1;
void upd_hld(int x,int y,int c)
{
if(pos[head[x]]<=pos[y])
{
st1.upd(1,1,n,pos[y],pos[x],c);
}
else
{
st1.upd(1,1,n,pos[head[x]],pos[x],c);
upd_hld(st[0][head[x]],y,c);
}
}
bool check2(int x)
{
s3=st1.get(1,1,n,pos[x],pos[x]);
if(s3==1) return 1;
return 0;
}
void upd(int x,int y)
{
for(int i=1; i<=m; i++)
{
if(i==x) continue;
s2=a[x].a;
s3=lca(s2,a[i].a);
s4=lca(s2,a[i].b);
if(s3==s2)
{
if(depth[s2]>=depth[a[i].c])
d[i]+=y;
}
else if(s4==s2)
{
if(depth[s2]>=depth[a[i].c])
d[i]+=y;
}
}
}
void phongbeo()
{
cin>>n;
// st1.build(1,1,n);
// dem=0;
// for(int i=1; i<=n; i++)
// pos[i]=0,heavy[i]=0,head[i]=0,v[i].clear();
for(int i=1; i<n; i++)
{
cin>>l>>r;
v[l].pb(r);
v[r].pb(l);
}
dfs(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]];
des(1,1);
cin>>m;
for(int i=1; i<=m; i++)
cin>>a[i].a>>a[i].b,a[i].c=lca(a[i].a,a[i].b),
upd_hld(a[i].a,a[i].c,1),
upd_hld(a[i].b,a[i].c,1),
upd_hld(a[i].c,a[i].c,-1),
d[i]=0,
b[i]=0;
for(int i=1; i<=m; i++)
upd(i,1);
for(int i=1; i<=m; i++)
{
bool de=0;
for(int j=1; j<=m; j++)
{
if(b[j]) continue;
if(d[j]==0&&check2(a[j].b))
{
upd_hld(a[j].a,a[j].c,-1),
upd_hld(a[j].b,a[j].c,-1),
upd_hld(a[j].c,a[j].c,1);
upd(j,-1);
b[j]=1;
de=1;
s10=j;
break;
}
}
if(!de)
{
cout<<"No";
return;
}
}
cout<<"Yes";
}
/*
NO 1
NO 1
*/
Compilation message
jail.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
47 | main()
| ^~~~
jail.cpp: In member function 'void IT1::build(int, int, int)':
jail.cpp:115:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'void IT1::upd(int, int, int, int, int, int)':
jail.cpp:134:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
134 | int mid=l+r>>1;
| ~^~
jail.cpp: In member function 'int IT1::get(int, int, int, int, int)':
jail.cpp:143:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
143 | int mid=l+r>>1;
| ~^~
jail.cpp: In function 'int main()':
jail.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define fin(x) freopen(x".inp","r",stdin)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
jail.cpp:50:6: note: in expansion of macro 'fin'
50 | fin(task),fou(task);
| ^~~
jail.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | #define fou(x) freopen(x".out","w",stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
jail.cpp:50:16: note: in expansion of macro 'fou'
50 | fin(task),fou(task);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
