Submission #702458

#TimeUsernameProblemLanguageResultExecution timeMemory
702458MinhAnhndJail (JOI22_jail)C++14
21 / 100
5090 ms624 KiB
#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 1201 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]; long father[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]){ father[togo] = current_node; 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]){ 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]){ 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; } } }

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:76:10: warning: variable 'father' set but not used [-Wunused-but-set-variable]
   76 |     long father[sizeofA]={};
      |          ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...