#include <bits/stdc++.h> #include "gift.h" using namespace std; using ll = long long; class DisjointUnionSets { vector<int> rank, parent, next; public: DisjointUnionSets(int n){ rank.assign(n, 0); parent.resize(n); next.resize(n); for (int i=0; i<n; i++){ parent[i]=i; next[i]=i; } } int find(int i){ if (parent[i]==i) return i; return parent[i]=find(parent[i]); } int getNext(int i){ if (next[i]==i) return i; return next[i]=getNext(next[i]); } 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]++; } } void unionRange(int l, int r){ for (int i = l+1; i <= r; i++){ unionSets(l, i); } } }; 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()); for (int i=0; i<r; i++){ if (arr[i][0]==1){ dus.unionRange(arr[i][1], 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; }