Submission #329782

#	Time	Username	Problem	Language	Result	Execution time	Memory
329782		northlake	Handcrafted Gift (IOI20_gift)	C++17	60 / 100	1570 ms	15576 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) {
            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