#include <bits/stdc++.h> #include "gift.h" using namespace std; using ll = long long; class DisjointUnionSets { vector<int> rank, parent; public: DisjointUnionSets(int n){ rank.resize(n, 0); parent.resize(n); for (int i=0; i<n; i++){ parent[i]=i; } } int find(int i){ int root=parent[i]; if (parent[root]!=root){ return parent[i]=find(root); } return root; } void unionSets(int x, int y){ int xRoot=find(x); int yRoot=find(y); if (xRoot==yRoot) return; if (rank[xRoot]<rank[yRoot]){ parent[xRoot]=yRoot; } else if (rank[yRoot]<rank[xRoot]){ parent[yRoot]=xRoot; } else{ parent[yRoot]=xRoot; rank[xRoot]++; } } }; int construct(int n, int r, vector <int> a, vector <int> b, vector <int> x){ string s=""; vector<vector<int>> arr(r); DisjointUnionSets dus(n); vector<int> visited(n, -1); int alx = 1; for (int i=0; i<r; i++){ if (a[i]==b[i] && x[i]==2){return 0;} if (x[i]==2){alx=0;} } if (alx==1){ for (int i=0; i<n; i++){ s.push_back('R'); } craft(s); return 1; } for (int i=0; i<r; i++){ arr[i].push_back(x[i]); arr[i].push_back(a[i]); arr[i].push_back(b[i]); } sort(arr.begin(),arr.end()); int last=-1; for (int i=0; i<r; i++){ if (arr[i][0]==1){ for (int i=max(last,arr[i][1]); i<arr[i][2]; i++){ dus.unionSets(i,i+1); } last=arr[i][2]; } else{ int comp1=dus.find(arr[i][1]); int comp2=dus.find(arr[i][2]); if (comp1==comp2){return 0;} } } int cur=1; s.push_back('R'); for (int i=1; i<n; i++){ int comp1=dus.find(i-1); int comp2=dus.find(i); if (comp1!=comp2){cur=1-cur;} if (cur){s.push_back('R');} else{s.push_back('B');} } craft(s); return 1; }