Submission #1013142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013142		ReLice	Jail (JOI22_jail)	C++14	77 / 100	5011 ms	231452 KiB

jail

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=2e5+7;
const ld eps=1e-9;
vector<vll> g(N);
vector<set<ll>> g2(N);
ll vis[N];
ll up[N][20],d[N];
ll mx;
bool flag;
vll s(N),t(N);
void dfs(ll v){
    chmax(mx,d[v]);
    for(ll i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
    for(auto i : g[v]){
        if(i==up[v][0])continue;
        up[i][0]=v;
        d[i]=d[v]+1;
        dfs(i);
    }
}
ll lca(ll a,ll b){
    if(d[a]<d[b])swap(a,b);
    for(ll i=19;i>=0;i--){
        if(d[a]-d[b]>=(1ll<<i)){
            a=up[a][i];
        }
    }
    if(a==b)return a;
    for(ll i=19;i>=0;i--){
        if(d[a]>(1ll<<i) && up[a][i]!=up[b][i]){
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}
bool on_path(ll a,ll b,ll x){
    ll k=lca(a,x),l=lca(b,x);
    ll lc=lca(a,b);
    if((k==x && l==lc) || (k==lc && l==x))return true;
    return false;
}
bool f[N];
void check(ll v){
    f[v]=1;
    vis[v]=1;
    if(flag)return;
    for(auto i : g2[v]){
        if(f[i])flag=true;
        else if(vis[i])continue;
        if(flag){f[v]=0;return;}
        check(i);

    }
    f[v]=0;
}
void build(ll a,ll b,ll x){
    ll lc=lca(a,b);
    while(a!=lc){
        if(s[a] && s[a]!=x) g2[s[a]].ins(x);
        if(t[a] && t[a]!=x) g2[x].ins(t[a]);
        a=up[a][0];
    }
    if(s[a] && s[a]!=x) g2[s[a]].ins(x);
    if(t[a] && t[a]!=x) g2[x].ins(t[a]);
    while(b!=lc){
        if(s[b] && s[b]!=x) g2[s[b]].ins(x);
        if(t[b] && t[b]!=x) g2[x].ins(t[b]);
        b=up[b][0];
    }

}
str solve(){
    ll i,j;
    ll n;
    cin>>n;
    flag=0;
    for(i=0;i<=n;i++){
        g[i].clear();
        vis[i]=0;
        t[i]=s[i]=0;
        for(j=0;j<20;j++)up[i][j]=0;
    }
    ll a,b;
    bool bamboo=1;
    for(i=1;i<n;i++){
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
        if(a+1!=b)bamboo=false;
    }
    d[i]=1;
    dfs(1);
    ll m;
    cin>>m;
    for(i=1;i<=m;i++)g2[i].clear();
    vector<pair<ll,ll> > v(1);
    vector<vll> v2(n+5);
    for(i=0;i<m;i++){
        cin>>a>>b;
        v.pb({a,b});
        v2[a].pb(i+1);
        v2[b].pb(i+1);
    }
    if(bamboo){
        bool f=0;
        deque<ll> dq;
        map<ll,ll> mp;
        for(i=1;i<=n;i++){
            if(v2[i].sz>1){
                if(mp[v2[i][0]]==mp[v2[i][1]]) return "No";
                if(mp[v2[i][1]]) swap(v2[i][0],v2[i][1]);
                if(dq[0]!=v2[i][0])return "No";
                dq.pof;
                dq.pb(v2[i][1]);
                mp[dq.bc]++;
            }
            else if(v2[i].sz){
                ll a=v2[i][0];
                if(mp[a]){
                    if(dq[0]!=a) return "No";
                    dq.pof;
                }else {
                    if(!dq.sz)f=(v[a].fr<v[a].sc);
                    else if(f!=(v[a].fr<v[a].sc))return "No";
                    dq.pb(a);
                    mp[a]++;
                }
            }
        }
        return "Yes";
    }
    if(mx<=20){
        for(i=1;i<=m;i++){
            s[v[i].fr]=i;
            t[v[i].sc]=i;
        }
        for(i=1;i<=m;i++){
            build(v[i].fr,v[i].sc,i);
        }
    }
    else{
        for(i=1;i<=m;i++){
            for(j=1;j<=m;j++){
                if(i==j) continue;
                bool s=on_path(v[i].fr,v[i].sc,v[j].fr),t=on_path(v[i].fr,v[i].sc,v[j].sc);
                if(s)g2[j].ins(i);
                if(t)g2[i].ins(j);
            }
        }
    }
    for(i=1;i<=m;i++){
        if(!vis[i]){
            check(i);
            if(flag)return "No";
        }
    }
    return "Yes";
}
signed main(){
    start();
    ll t=1;
    cin>>t;
    while(t--) cout<<solve()<<endl;
    return 0;
}
/*
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8




*/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23