Submission #2831480


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

struct UnionFind{
  Int n;
  vector<Int> r,p;
  UnionFind(){}
  UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  Int find(Int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y){
    x=find(x);y=find(y);
    if(x==y) return;
    r[x]+=r[y];
    p[y]=x;
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  
  vector<set<Int> > G(n),H(n);
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace(y);
    G[y].emplace(x);
  }
  using P = pair<Int, Int>;
  queue<P> q;
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    if(G[x].count(y)) q.emplace(x,y);
    H[x].emplace(y);
    H[y].emplace(x);
  }

  UnionFind uf(n);
  while(!q.empty()){
    Int x,y;
    tie(x,y)=q.front();q.pop();
    if(uf.same(x,y)) continue;
    x=uf.find(x);y=uf.find(y);
    
    uf.unite(x,y);
    
    for(auto z:H[y]){
      if(G[x].count(z)) q.emplace(x,z);
      H[x].emplace(z);
      H[z].emplace(x);
    }    
    for(auto z:G[y]){
      if(H[x].count(z)) q.emplace(x,z);
      G[x].emplace(z);
      G[z].emplace(x);
    }
  }
  cout<<(uf.r[uf.find(0)]==n?"YES":"NO")<<endl;
  return 0;
}

Submission Info

Submission Time
Task E - Blue and Red Tree
User beet
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 1367 Byte
Status AC
Exec Time 1259 ms
Memory 125056 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 3
AC × 53
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt AC 1 ms 256 KB
in10.txt AC 183 ms 29952 KB
in11.txt AC 1006 ms 95232 KB
in12.txt AC 1023 ms 100480 KB
in13.txt AC 1229 ms 125056 KB
in14.txt AC 1029 ms 100992 KB
in15.txt AC 1095 ms 108416 KB
in16.txt AC 1142 ms 112768 KB
in17.txt AC 983 ms 94976 KB
in18.txt AC 1059 ms 103552 KB
in19.txt AC 1199 ms 120192 KB
in2.txt AC 1 ms 256 KB
in20.txt AC 1018 ms 97408 KB
in21.txt AC 1051 ms 102016 KB
in22.txt AC 1050 ms 102528 KB
in23.txt AC 1051 ms 103040 KB
in24.txt AC 1094 ms 106880 KB
in25.txt AC 1037 ms 100480 KB
in26.txt AC 1147 ms 109312 KB
in27.txt AC 1163 ms 109824 KB
in28.txt AC 1105 ms 109440 KB
in29.txt AC 1097 ms 105216 KB
in3.txt AC 1 ms 256 KB
in30.txt AC 1259 ms 122752 KB
in31.txt AC 626 ms 48640 KB
in32.txt AC 638 ms 48768 KB
in33.txt AC 644 ms 48640 KB
in34.txt AC 630 ms 48640 KB
in35.txt AC 683 ms 48640 KB
in36.txt AC 665 ms 48640 KB
in37.txt AC 661 ms 48768 KB
in38.txt AC 584 ms 48640 KB
in39.txt AC 584 ms 48640 KB
in4.txt AC 185 ms 29952 KB
in40.txt AC 590 ms 48640 KB
in41.txt AC 617 ms 48640 KB
in42.txt AC 615 ms 48640 KB
in43.txt AC 622 ms 48768 KB
in44.txt AC 622 ms 48640 KB
in45.txt AC 624 ms 48640 KB
in46.txt AC 601 ms 48640 KB
in47.txt AC 608 ms 48640 KB
in5.txt AC 183 ms 29952 KB
in6.txt AC 598 ms 48640 KB
in7.txt AC 185 ms 29952 KB
in8.txt AC 186 ms 29952 KB
in9.txt AC 186 ms 29952 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB