| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1321330 | eri16 | Handcrafted Gift (IOI20_gift) | C++20 | 0 ms | 0 KiB |
#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)
}
}
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;
}