Submission #1013101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013101		ReLice	Jail (JOI22_jail)	C++17	0 / 100	21 ms	14912 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];
bool flag;
void dfs(ll 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;
}
map<ll,ll> p;
void check(ll v){
    p[v]=1;
    if(flag)return;
    for(auto i : g2[v]){
        if(p[i])flag=true;
        else if(vis[i])continue;
        if(flag)return;
        vis[i]=vis[v];
        check(i);
    }
    p[v]=0;
}
str solve(){
    ll i,j;
    ll n;
    cin>>n;
    flag=0;
    for(i=0;i<=n;i++){
        g[i].clear();
        vis[i]=0;
        for(j=0;j<20;j++)up[i][j]=0;
    }
    ll a,b;
    for(i=1;i<n;i++){
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    d[i]=1;
    dfs(1);
    ll m;
    cin>>m;
    for(i=1;i<=m;i++)g2[i].clear();
    vector<pair<ll,ll> > v(1);
    for(i=0;i<m;i++){
        cin>>a>>b;
        v.pb({a,b});
    }
    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);
        }
    }
    ll c=0;/*
    for(i=1;i<=m;i++){
        for(auto j : g2[i]) cout<<i<<' '<<j<<endl;
    }*/
    for(i=1;i<=m;i++){
        if(!vis[i]){
            vis[i]=++c;
            check(i);
            if(flag)return "No";
        }
    }
    return "Yes";
}
signed main(){
    start();
    ll t=1;
    cin>>t;
    while(t--) cout<<solve()<<endl;
    return 0;
}
/*
1
6
1 2
2 3
3 4
4 5
5 6
4
3 1
4 2
5 3
6 4




*/

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