Submission #546941

#	Time	Username	Problem	Language	Result	Execution time	Memory
546941		ngrace	Jail (JOI22_jail)	C++14	61 / 100	5093 ms	26728 KiB

jail

#include <vector>
#include <iostream>
#include <utility>
#include <set>
#include <algorithm>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second

int N,M;
int anc=20;
v<v<int>> adj;
v<int> depth;
v<v<int>> par;
void dfs(int cur, int from){
    if(depth[cur]!=-1) return;
    depth[cur]=depth[from]+1;
    par[cur][0]=from;
    for(int it:adj[cur]) dfs(it, cur);
}
bool is_anc(int cur, int other){
    for(int i=anc-1; i>=0; i--){
        if(depth[par[cur][i]]>=depth[other]) cur=par[cur][i];
    }
    if(cur==other) return true;
    return false;
}

int lca(int a, int b){
    if(depth[a]<depth[b]) swap(a,b);
    for(int i=anc-1; i>=0; i--){
        if(depth[par[a][i]]>=depth[b]) a=par[a][i];
    }
    if(a==b) return a;
    for(int i=anc-1; i>=0; i--){
        if(par[a][i]!=par[b][i]){
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}
bool path(int a, int b, int c){//does c lie on the path of a and b
    int l=lca(a,b);
    if(is_anc(c,l) && (is_anc(a,c)||is_anc(b,c))) return true;
    return false;
}

v<bool> prevrec;
v<bool> vis;
bool find_cycle(int cur){
    if(!vis[cur]){
        vis[cur]=true;
        prevrec[cur]=true;
        for(int it:adj[cur]){
            if(!vis[it] && find_cycle(it)){
                return true;
            }
            else if(prevrec[it]){
                return true;
            }
        }
    }
    prevrec[cur]=false;
    return false;
}

int main(){
    int Q;
    cin>>Q;
    for(int q=0;q<Q;q++){
        cin>>N;
        adj=v<v<int>>(N);
        for(int i=0; i<N-1; i++){
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        depth=v<int>(N,-1);
        par=v<v<int>>(N,v<int>(anc,-1));
        dfs(0,0);
        for(int i=1; i<anc; i++){
            for(int j=0; j<N; j++){
                par[j][i]=par[par[j][i-1]][i-1];
            }
        }

        cin>>M;
        v<pii> rooms(M);
        for(int i=0; i<M; i++){
            cin>>rooms[i].fi>>rooms[i].se;
            rooms[i].fi--;
            rooms[i].se--;
        }

        adj = v<v<int>>(M);
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++){
                if(i==j) continue;
                bool sj=path(rooms[i].fi, rooms[i].se, rooms[j].fi);
                bool ej=path(rooms[i].fi, rooms[i].se, rooms[j].se);

                if(sj) adj[j].push_back(i);
                if(ej) adj[i].push_back(j);
            }
        }


        bool cycle=false;
        vis = v<bool>(M,false);
        prevrec = v<bool>(M,false);
        for(int i=0; i<M; i++){
            if(!vis[i] && find_cycle(i)){
                cycle=true;
                break;
            }
        }

        if(cycle) cout<<"No\n";
        else cout<<"Yes\n";
    }
}

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