| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 874667 |
2023-11-17T14:20:31 Z |
winter0101 |
Jail (JOI22_jail) |
C++14 |
|
40 ms |
70740 KB |
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=1e5+2e4+9;
vector<int>a[maxn];
pii b[maxn];
int sub[maxn];
int d[maxn],p[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto &v:a[u]){
if (v==par)continue;
d[v]=d[u]+1;
p[v]=u;
dfs(v,u);
sub[u]+=sub[v];
if (a[u][0]==par||sub[a[u][0]]<sub[v])swap(a[u][0],v);
}
}
int pos[maxn],h[maxn],tle=0,rev[maxn];
void hld(int u,int par,int head){
pos[u]=++tle;
h[u]=head;
if (a[u][0]!=par){
hld(a[u][0],u,head);
}
for (auto v:a[u]){
if (v==par||v==a[u][0])continue;
hld(v,u,v);
}
}
vector<int>g[maxn*9];//two segtree and m
bool fl=1;
int low[maxn*9],num[maxn*9],tme=0;
int n,m;
void build(int id,int l,int r){
if (l==r){
rev[l]=id;
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
//->
g[id].pb(id*2);
g[id].pb(id*2+1);
g[id*2+4*n].pb(id+4*n);
g[id*2+1+4*n].pb(id+4*n);
}
void addedg(int id,int l,int r,int u,int v,int ver){
if (l>v||r<u||u>v)return;
//cout<<l<<" "<<r<<" "<<u<<" "<<v<<'\n';
if (u<=l&&r<=v){
g[ver+8*n].pb(id);
g[id+4*n].pb(ver+8*n);
return;
}
int mid=(l+r)/2;
addedg(id*2,l,mid,u,v,ver);
addedg(id*2+1,mid+1,r,u,v,ver);
}
void takepath(int id,int u,int v){
bool f1=1,f2=1;
while (h[u]!=h[v]){
if (d[h[u]]<d[h[v]]){
swap(f1,f2);
swap(u,v);
}
addedg(1,1,n,pos[h[u]],pos[u]-f1,id);
f1=0;
u=p[h[u]];
}
if (pos[u]>pos[v]){
swap(u,v);
swap(f1,f2);
}
addedg(1,1,n,pos[u]+f1,pos[v]-f2,id);
}
stack<int>t;
void redfs(int u){
t.push(u);
low[u]=num[u]=++tme;
for (auto v:g[u]){
if (num[v]==-1)continue;
if (num[v])low[u]=min(low[u],low[v]);
else {
redfs(v);
low[u]=min(low[u],low[v]);
}
}
if (low[u]==num[u]){
int dem=0;
while (!t.empty()&&t.top()!=u){
num[t.top()]=-1;
dem+=(t.top()>8*n);
t.pop();
}
dem+=(u>8*n);
if (dem>1)fl=0;
num[u]=-1;
t.pop();
}
}
int t1[maxn];
void solve(){
cin>>n;
for1(i,1,n){
a[i].clear();
t1[i]=0;
}
for1(i,1,9*n){
g[i].clear();
num[i]=low[i]=0;
}
for1(i,1,n-1){
int u,v;
cin>>u>>v;
a[u].pb(v);
a[v].pb(u);
}
dfs(1,0);
tle=0;
hld(1,0,1);
build(1,1,n);
cin>>m;
for1(i,1,m){
cin>>b[i].fi>>b[i].se;
g[i+8*n].pb(rev[pos[b[i].fi]]+4*n);
g[rev[pos[b[i].se]]].pb(i+8*n);
t1[b[i].se]=i;
takepath(i,b[i].fi,b[i].se);
}
for1(i,1,m){
if (t1[b[i].fi]){
g[i+8*n].pb(t1[b[i].fi]+8*n);
//cout<<i<<" "<<t1[b[i].fi]<<'\n';
}
}
//takepath(2,b[2].fi,b[2].se);
tme=0;
fl=1;
for1(i,1,8*n+m)if (!num[i])redfs(i);
if (fl)cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
int test=1;
cin>>test;
while (test--)solve();
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:163:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | freopen("temp.INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
70740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
70740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
70740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
70740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
70740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
70720 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
70740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
