Submission #1246571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246571		damoon	Jail (JOI22_jail)	C++20	49 / 100	5094 ms	23044 KiB

jail

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define mid (l+r)/2
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
#define dig(x,d) ((x&(1ll<<d)) > 0)

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}
string pr(bool* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i];return"";}
ostream& operator <<(ostream& out, pii x){out << "("<<x.f<<", "<<x.s<<") ";return out;}

random_device device;
default_random_engine rng(device());
#define randt(a,b) uniform_int_distribution<int64_t>(a,b)(rng)

const int L=2e5+10, mod=1e9+7;
const int inf=1e9+10;
int n,m;
int st[L],fn[L],par[L],tim;
int S[L],F[L],ind[L];
bool mark[L];
vector<int> adj[L],adj2[L],tp;
vector<pii> edge;

void dfsT(int v){
    st[v] = ++tim;
    for(auto u:adj[v]){
        if(u != par[v]){
            par[u] = v;
            dfsT(u);
        }
    }
    fn[v] = ++tim;
}

bool ispar(int u,int v){
    return (st[u] <= st[v] and fn[u] >= fn[v]);
}

int lca(int u,int v){
    while(!ispar(u,v)){
        u = par[u];
    }
    return u;
}

bool isin(int u,int v,int w){
    return ((ispar(w,u) xor ispar(w,v)) or w == lca(u,v));
}

void reset(){
    tp.clear();
    edge.clear();
    for(int i=1;i<=n;i++){
        adj[i].clear();
        adj2[i].clear();
        mark[i] = 0;
    }
}

void dfs(int v){
    mark[v] = 1;
    for(auto u:adj2[v]){
        if(!mark[u])
            dfs(u);
    }
    tp.pb(v);
}

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in.in");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;
    for(int gg=0;gg<t;gg++){
        cin>>n;
        reset();
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>S[i]>>F[i];
        }
        dfsT(1);

        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                if(i == j)
                    continue;
                if(isin(S[i],F[i],F[j]) or isin(S[j],F[j],S[i])){
                    //cout<<"ee: "<<i<<"  "<<j<<endl;
                    adj2[i].pb(j);
                }
            }
        }

        for(int i=1;i<=m;i++){
            for(auto u:adj2[i]){
                edge.pb(pii(i,u));
            }
            //cout<<i<<" --> "<<pr(adj2[i])<<endl;
        }
        for(int i=1;i<=m;i++){
            if(!mark[i])
                dfs(i);
        }
        reverse(all(tp));
        for(int i=0;i<m;i++){
            ind[tp[i]] = i;
        }

        bool ok = 1;
        for(auto e:edge){
            ok = ok and (ind[e.f] < ind[e.s]);
        }
        if(ok)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
}

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