Submission #329775

#	Time	Username	Problem	Language	Result	Execution time	Memory
329775		northlake	Handcrafted Gift (IOI20_gift)	C++17	60 / 100	1577 ms	22824 KiB

gift

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

using namespace std;

int find_ancestor(int uf[], int x) {
    while (x != uf[x]) {
        x = uf[x];
    }
    return x;
}

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

    for (int i = 0; i < r; i++) {
        if (x[i] == 1) {
            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: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 0 / 30