제출 #329781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
329781		northlake	Handcrafted Gift (IOI20_gift)	C++17	15 / 100	175 ms	16232 KiB

gift

#include<gift.h>
#include<bits/stdc++.h>

using namespace std;

int find_ancestor(vector<int>& uf, int x) {
    if (uf[x] == x) return x;
    int answer = find_ancestor(uf, uf[x]);
    uf[x] = answer;
    return answer;
}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    vector<int> union_find {};
    for (int i = 0; i < n; i++) {
        union_find.push_back(i);
    }

    for (int i = 0; i < r; i++) {
        if (x[i] == 1) {
            cout << a[i] << '\n';
            for (int j = a[i]+1; j <= b[i]; j++) {
                union_find[j] = union_find[a[i]];
            }
        }
    }

    for (int i = 0; i < r; i++) {
        if (x[i] == 2) {
            if (find_ancestor(union_find, a[i]) == find_ancestor(union_find, b[i])) return 0;
        }
    }

    string s = "R";
    bool red = true;
    for (int i = 1; i < n; i++) {
        if (find_ancestor(union_find, i) != find_ancestor(union_find, i-1)) red = !red;
        if (red) s += 'R';
        else s += 'B';
    }

    craft(s);
    return 1;
}

• Subtask 1: 0 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30