Submission #702514

#	Time	Username	Problem	Language	Result	Execution time	Memory
702514		MinhAnhnd	Jail (JOI22_jail)	C++14	21 / 100	5034 ms	15276 KiB

jail

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define ll unsigned long long

using namespace __gnu_pbds;

#define modu 1000000007
#define sizeofA 120001
int sum(ll a,ll b){
	return ((a % modu) + (b % modu))% modu;
}

typedef tree<long,null_type,less<long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

long max_ = 0;
ordered_set higher;
long N,M;
vector<long> adj[sizeofA];
vector<long> hyper_adj[sizeofA];
bool the_path[sizeofA] = {};
bool filling[sizeofA] = {};
//hyper_adj[a] -> b then (a before b)
bool check_valid(long now){
    if(the_path[now]){return 0;}

    the_path[now] = 1;
    filling[now] = 1;

    for (auto godo: hyper_adj[now]){
        //cout<<godo<<" "<<now<<endl;
        if(!check_valid(godo)){
            the_path[now] = 0;
            return 0;
        }
    }


    the_path[now] = 0;
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);
    ll t;
    cin>>t;
    while(t--){
    cin>>N;
    //memset(the_path, 0, sizeof(the_path));
    memset(filling, 0, sizeof(N+1));
    for(long i = 1;i<=N+1;i++){
        adj[i].clear();
        hyper_adj[i].clear();
    }
    long start[N+1]={};
    long work[N+1] ={};

    for(long i = 1;i<=N-1;i++){
        long temp1, temp2;
        cin>>temp1>>temp2;
        adj[temp1].push_back(temp2);
        adj[temp2].push_back(temp1);
    }
    cin>>M;
    for (long i = 1;i<=M;i++){
        long temp1, temp2;
        cin>>temp1>>temp2;
        start[temp1]=i;
        work[temp2]=i;
    }
    vector<long> children[sizeofA];
    stack<long> tovisit;
    stack<long> dfs;

    bool visited[sizeofA] = {};
    dfs.push(1);
    while(!dfs.empty()){
        long current_node = dfs.top();
        dfs.pop();
        visited[current_node] = 1;
        tovisit.push(current_node);
        for (auto togo : adj[current_node]){
            if (!visited[togo]){
                children[current_node].push_back(togo);
                dfs.push(togo);
            }
        }
    }
    multiset<long> beg[sizeofA];
    stack<long> to_remove;
    while(!tovisit.empty()){
        long current_node = tovisit.top();

        for(auto child : children[current_node]){
            if (beg[current_node].size() < beg[child].size()) {
				swap(beg[current_node], beg[child]);
			}
			for (auto item : beg[child]) {
                beg[current_node].insert(item);
                to_remove.push(item);
            }
        }

        if(start[current_node]!=0){
            long begin_ = start[current_node];
            for(auto item: beg[current_node]){
                //begin_ before item
                //find first item
                if (begin_ !=item) hyper_adj[begin_].push_back(item);
            }
        }

        if(work[current_node]!=0){
            long end_ = work[current_node];
            for(auto item: beg[current_node]){
                //end_ after item
                //first last item
                if(end_ != item) hyper_adj[item].push_back(end_);
            }
        }

        if((start[current_node]>0)&&(work[current_node]>0)){
            hyper_adj[start[current_node]].push_back(work[current_node]);
        }

        if(start[current_node]!=0){
            beg[current_node].insert(start[current_node]);
            to_remove.push(start[current_node]);
        }
        if(work[current_node]!=0){
            beg[current_node].insert(work[current_node]);
            to_remove.push(work[current_node]);
        }


        while(!to_remove.empty()){
            auto it = to_remove.top();
            auto counter = beg[current_node].count(it);
            if (counter > 1) beg[current_node].erase(it);
            to_remove.pop();
            //cout<<it<<" "<<counter<<endl;
        }

        tovisit.pop();
        //cout<<current_node<<" "<<beg[current_node].size()<<endl;
        //cout<<current_node<<" "<<start[current_node]<<" "<<work[current_node]<<endl;
    }
    bool checking = 1;
    for (long i = 1;i<=N;i++){
        if(!filling[i]){
            checking = checking & check_valid(i);
            if (checking == 0){
                break;
            }
        }
    }

    if (checking){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    }
}

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