| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 706589 |
2023-03-07T06:18:02 Z |
pcc |
Jail (JOI22_jail) |
C++14 |
|
67 ms |
9804 KB |
#include <bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pii pair<int,int>
const int mxn = 2e5+10;
int bit[mxn],idx[mxn],sz[mxn],link_top[mxn],fa[mxn],bs[mxn],dep[mxn];
bitset<mxn> del;
vector<int> tree[mxn];
vector<pii> ask[mxn];
pii dfn[mxn];
int mv[mxn];
int n,m;
int cnt = 0;
vector<pii> req;
bool flag = true;
void modify(int p,int s,int v){
if(p>s)return;
for(;p<=s;p+= p&-p)bit[p] += v;
return;
}
int getval(int p){
int re = 0;
for(;p>0;p-=p&-p)re += bit[p];
return re;
}
void find_sz(int now,int par){
sz[now] = 1;
bs[now] = 0;
for(auto nxt:tree[now]){
if(del[nxt]||nxt == par)continue;
dep[nxt] = dep[now]+1;
find_sz(nxt,now);
if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
sz[now] += sz[nxt];
}
// cout<<now<<":"<<sz[now]<<endl;
return;
}
int find_centroid(int now,int par,int tar){
for(auto nxt:tree[now]){
if(nxt == par||del[nxt])continue;
if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
}
return now;
}
void dfs2(int now,int par,int top){
fa[now] = par;
link_top[now] = top;
dfn[now].fs = ++cnt;
if(bs[now])dfs2(bs[now],now,top);
for(auto nxt:tree[now]){
if(nxt == par||del[nxt]||bs[now] == nxt)continue;
dfs2(nxt,now,nxt);
}
dfn[now].sc = ++cnt;
return;
}
int lca(int a,int b){
if(b == -1){
while(a != fa[link_top[a]])a = fa[link_top[a]];
return a;
}
int ta = link_top[a],tb = link_top[b];
while(ta != tb){
if(dep[ta]<dep[tb]){
swap(ta,tb);
swap(a,b);
}
a = fa[ta];
ta = link_top[a];
}
if(dep[a]<dep[b])return a;
else return b;
}
vector<pii> st;
bool dfs(int now,int par,int nowcen,bool tocen,bool useflag){
mv[now] = 0;
vector<pii> v;
for(auto nxt:tree[now]){
if(nxt == par||del[nxt])continue;
tocen = (tocen||dfs(nxt,now,nowcen,false,true));
mv[now] += mv[nxt];
}
for(auto &i:ask[now]){
if(lca(i.fs,i.sc) != nowcen)v.push_back(i);
else req.push_back(i);
mv[now]++;
if(tocen&&useflag)flag = false;
if(i.sc == nowcen)tocen = true;
else{
if(getval(dfn[i.sc].sc)-getval(dfn[i.sc].fs-1) != 0&&useflag)flag = false;
modify(dfn[i.sc].fs,cnt,1);
st.push_back({dfn[i.sc].fs,1});
}
}
// cout<<now<<' '<<par<<' '<<nowcen<<endl;
ask[now] = v;
return tocen;
}
int get_high(int now,int par){
int re = 1e9;
for(auto &i:ask[now]){
// cout<<now<<' '<<i.sc<<endl;
re = min(dep[i.sc],re);
}
for(auto nxt:tree[now]){
if(del[nxt]||nxt == par)continue;
re = min(re,get_high(nxt,now));
}
return re;
}
void cd(int now){
req.clear();
find_sz(now,now);
int cen = find_centroid(now,now,(sz[now]+1)/2);
// cout<<now<<','<<cen<<endl;
dep[cen] = 1;
find_sz(cen,cen);
cnt = 0;
dfs2(cen,cen,cen);
// cout<<cen<<endl;
for(auto nxt:tree[cen]){
// cout<<now<<','<<nxt<<','<<flag<<endl;
if(del[nxt])continue;
dfs(nxt,cen,cen,false,true);
if(!ask[cen].empty()){
if(lca(ask[cen][0].sc,nxt) == nxt){
if(get_high(nxt,cen) < dep[ask[cen][0].sc])flag = false;
}
}
while(!st.empty()){
modify(st.back().fs,cnt,-st.back().sc);
st.pop_back();
}
}
del[cen] = true;
for(auto nxt:tree[cen]){
if(del[nxt])continue;
find_sz(nxt,nxt);
dfs2(nxt,nxt,nxt);
}
map<int,int> deg;
map<int,vector<int>> paths;
set<int> all;
for(auto &i:req){
if(i.sc == cen){
paths[cen].push_back(lca(i.fs,-1));
deg[lca(i.fs,-1)]++;
all.insert(cen);
all.insert(lca(i.fs,-1));
}
else{
deg[lca(i.fs,-1)]++;
paths[lca(i.sc,-1)].push_back(lca(i.fs,-1));
all.insert(lca(i.fs,-1));
all.insert(lca(i.sc,-1));
}
}
for(auto &i:ask[cen]){
paths[lca(i.sc,-1)].push_back(cen);
deg[cen]++;
}
queue<int> q;
all.insert(cen);
if(!deg[cen])deg[cen] = 0;
for(auto nxt:tree[cen]){
if(!deg[nxt])deg[nxt] = 0;
all.insert(nxt);
if(del[nxt]||!mv[nxt])continue;
// cout<<cen<<' '<<nxt<<":"<<mv[nxt]<<endl;
paths[cen].push_back(nxt);
deg[nxt]++;
}
for(auto &i:all){
// cout<<i<<":";cout<<deg[i]<<';';
// for(auto &j:paths[i])cout<<j<<',';cout<<endl;
if(!deg[i])q.push(i);
}
while(!q.empty()){
auto now = q.front();
q.pop();
for(auto nxt:paths[now]){
if(!deg[nxt])continue;
// cout<<now<<':'<<nxt<<endl;
deg[nxt]--;
if(!deg[nxt])q.push(nxt);
}
}
// for(auto &i:deg)cout<<i.fs<<":"<<i.sc<<',';cout<<endl<<endl;
for(auto &i:deg)if(i.sc)flag = false;
// cout<<flag<<endl<<endl;
// cout<<now<<endl;
del[cen] = true;
for(auto nxt:tree[cen]){
if(del[nxt])continue;
cd(nxt);
}
return;
}
void solve(){
flag = true;
cin>>n;
for(int i = 1;i<n;i++){
int a,b;
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
cin>>m;
req = vector<pii>(m);
for(int i = 0;i<m;i++){
int a,b;
cin>>a>>b;
ask[a].push_back({a,b});
}
cd(1);
if(flag)cout<<"Yes\n";
else cout<<"No\n";
for(int i = 1;i<=n;i++){
tree[i].clear();
ask[i].clear();
cnt = 0;
del[i] = false;
}
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}
/*
1
3
1 2
2 3
1
1 3
1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
67 ms |
9788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9756 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
9804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9756 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
9804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9756 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
9804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9756 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
9804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9768 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 5 |
Incorrect |
25 ms |
9772 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
67 ms |
9788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
