konchin_shih

pH

Nov 13th, 2022
749
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<functional>
  5. #include<numeric>
  6. #include<cstdlib>
  7. using namespace std;
  8. namespace {
  9.     template<typename T> using V=vector<T>;
  10.     template<typename T1,typename T2=T1> using P=pair<T1,T2>;
  11.     template<typename T> using F=function<T>;
  12.     using ll=long long;
  13. }
  14. constexpr int maxn=1e6+5;
  15. static inline void solve(){
  16.     int n;cin>>n;
  17.     V<int> h(n),w(n);
  18.     for(auto& i:h) cin>>i;
  19.     for(auto& i:w) cin>>i;
  20.     V<V<int>> e(maxn);
  21.     V<int> in(maxn,0),dsu(maxn);
  22.     iota(dsu.begin(),dsu.end(),0);
  23.     F<int(int)> find=[&](int x){
  24.         return x==dsu[x]?x:dsu[x]=find(dsu[x]);
  25.     };
  26.     auto merge=[&](int a,int b){dsu[find(a)]=find(b);};
  27.     for(int i=0;i<n;i++){
  28.         e[h[i]].emplace_back(w[i]),in[w[i]]++;
  29.         merge(h[i],w[i]);
  30.     }
  31.     int pos=0,neg=0,s=-1,t=-1;
  32.     for(int i=0;i<maxn;i++){
  33.         if((int)e[i].size()<in[i]) pos++,t=i;
  34.         if(in[i]<(int)e[i].size()) neg++,s=i;
  35.         if(abs((int)e[i].size()-in[i])>1) {
  36.             cerr<<i<<' '<<in[i]<<' '<<e[i].size()<<endl;
  37.             goto ICANT;
  38.         }
  39.     }
  40.     if(P{pos,neg}!=P{0,0}&&P{pos,neg}!=P{1,1})
  41.         goto ICANT;
  42.     if(!~s) for(int i=0;i<maxn;i++)
  43.         if(e[s=t=i].size()>0) break;
  44.     for(int i=0;i<maxn;i++)
  45.         if((in[i]||e[i].size())&&find(i)!=find(s)){
  46.             cerr<<i<<endl;
  47.             goto ICANT;
  48.         }
  49.     cout<<s<<' '<<t<<endl;
  50.     return;
  51. ICANT:
  52.     cout<<-1<<endl;
  53. }
  54. int main(){
  55.     int T=1;
  56.     cin>>T;
  57.     while(T--)
  58.         solve();
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment