Submission #546949

#	Time	Username	Problem	Language	Result	Execution time	Memory
546949		ngrace	Jail (JOI22_jail)	C++14	60 / 100	5066 ms	58828 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;
v<v<int>> adj;
v<int> pathstarts;
v<int> pathends;
v<set<int>> sets;
v<v<int>> diadj;
void dfs(int cur, int par){
    for(int it:adj[cur]){
        if(it==par) continue;
        dfs(it, cur);

        for(int i:sets[it]){
            if(i<0) continue;

            if(sets[it].find(-1-i)!=sets[it].end()) continue;
            
            if(sets[cur].find(i)==sets[cur].end()) sets[cur].insert(i);
            else sets[cur].insert(-1-i);
        
            if(pathstarts[cur]!=-1 && pathstarts[cur]!=i){
                //cout<<"start of path "<<pathstarts[cur]<<" lies on path "<<i<<endl;
                diadj[pathstarts[cur]].push_back(i);
            }
            if(pathends[cur]!=-1 && pathends[cur]!=i){
                //cout<<"end of path "<<pathends[cur]<<" lies on path "<<i<<endl;
                diadj[i].push_back(pathends[cur]);
            }
        }
    }
    if(pathstarts[cur]!=-1){
        if(sets[cur].find(pathstarts[cur])==sets[cur].end()) sets[cur].insert(pathstarts[cur]);
        else sets[cur].insert(-1-pathstarts[cur]);
    }
    if(pathends[cur]!=-1){
        if(sets[cur].find(pathends[cur])==sets[cur].end()) sets[cur].insert(pathends[cur]);
        else sets[cur].insert(-1-pathends[cur]);
    }

    if(pathstarts[cur]!=-1 && pathends[cur]!=-1){
        //cout<<"end of path "<<pathends[cur]<<" lies on path "<<pathstarts[cur]<<endl;
        diadj[pathstarts[cur]].push_back(pathends[cur]);
    }

    for(int it:adj[cur]){
        if(it==par) continue;
        sets[it].clear();
    }
}

v<bool> prevrec;
v<bool> vis;
bool find_cycle(int cur){
    if(!vis[cur]){
        vis[cur]=true;
        prevrec[cur]=true;
        for(int it:diadj[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);
        }

        cin>>M;
        pathstarts = v<int>(N,-1);
        pathends=v<int>(N,-1);
        for(int i=0; i<M; i++){
            int s,e;
            cin>>s>>e;
            s--;
            e--;
            pathstarts[s]=i;
            pathends[e]=i;
        }

        diadj = v<v<int>>(M);
        sets = v<set<int>>(N);
        dfs(0,0);

        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: 0 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23