Submission #546937

#	Time	Username	Problem	Language	Result	Execution time	Memory
546937		ngrace	Jail (JOI22_jail)	C++14	66 / 100	5070 ms	23300 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<int> stack;
v<bool> vis;
bool find_cycle(int cur){
    if(vis[cur]){
        for(int it:stack){
            if(it==cur) return true;
        }
        return false;
    }
    vis[cur]=true;
    stack.push_back(cur);
    for(int it:adj[cur]){
        bool b=find_cycle(it);
        if(b) return true;
    }
    stack.pop_back();
    return false;
}

int main(){
    int Q;
    cin>>Q;
    for(int q=0;q<Q;q++){
        cin>>N;
        adj=v<v<int>>(N);
        bool subone=true;
        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);
            if(a+1!=b) subone=false;
        }

        if(subone){
            cin>>M;
            v<pii> rooms(M);
            v<pii> rooms2(M);
            for(int i=0; i<M; i++){
                int a,b;
                cin>>a>>b;
                if(b>=a){
                    rooms.push_back({a,b});
                    rooms2.push_back({-a,b});
                    rooms2.push_back({-b,a});
                }
                else{
                    rooms.push_back({a,-b});
                    rooms.push_back({b,-a});
                    rooms2.push_back({-a,-b});
                }
            }

            sort(rooms.begin(), rooms.end());
            sort(rooms2.begin(),rooms2.end());

            pii cur={-1,-1};
            pii def={-1,-1};
            bool out=true;
            for(pii it:rooms){
                if(it.se<=0){
                    if(cur!=def && cur.se>=it.fi){
                        out=false;
                        break;
                    }
                }
                else{
                    if(it.se<cur.se){
                        out=false;
                        break;
                    }
                    cur=it;
                }
            }

            cur={1,1};
            def={1,1};
            for(pii it:rooms2){
                if(it.se>=0){
                    if(cur!=def && cur.se>=it.fi){
                        out=false;
                        break;
                    }
                }
                else{
                    if(it.se<cur.se && cur!=def){
                        out=false;
                        break;
                    }
                    cur=it;
                }
            }

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

            continue;
        }

        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);
        bool cycle=false;
        for(int i=0; i<M; i++){
            for(int j=i+1; j<M; j++){
                bool start1=path(rooms[j].fi, rooms[j].se, rooms[i].fi);
                bool start2=path(rooms[i].fi, rooms[i].se, rooms[j].fi);
                bool end1=path(rooms[j].fi, rooms[j].se, rooms[i].se);
                bool end2=path(rooms[i].fi, rooms[i].se, rooms[j].se);

                if((start1&&start2) || (start1&&end1) || (start2&&end2) || (end1&&end2)) cycle=true;
                if(cycle) break;

                if(start1 || end2) adj[i].push_back(j);
                if(start2 || end1) adj[j].push_back(i);
            }
            if(cycle) break;
        }

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

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

• Subtask 1: 5 / 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