제출 #756329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756329		1bin	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	292 ms	30616 KiB

gift

#include <bits/stdc++.h>
#include "gift.h"
using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 5e5 + 5;
int par[NMAX], nx[NMAX];
vector<tuple<int, int, int>> v;
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x){
    string s(n, 'B');
    for(int i = 0; i < r; i++) v.emplace_back(x[i], a[i], b[i]);
    sort(all(v));
    
    memset(par, -1, sizeof(par));
    for(int i = 0; i < n; i++) nx[i] = i + 1;
    for(auto&[x, a, b] : v){
        if(x == 1){
            a = find(a);
            for(int i = nx[a]; i <= b; i = nx[a]){
                int p = find(i);
                nx[a] = nx[p];
                par[p] = a;
            }
        }
        else if(find(a) == find(b)) return 0;
    }
    
    int f = 0;
    for(int i = 0; i < n; i++){
        if(find(i) == i) f ^= 1;
        if(f == 1) s[i] = 'R';
    }
    craft(s);
    //cout << s << '\n';
    return 1;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, r;
    cin >> n >> r;
    vector<int> a(n), b(n), x(n);
    for(int i = 0; i < r; i++) cin >> a[i] >> b[i] >> x[i];
    construct(n, r, a, b, x);
    return 0;
}
*/

/*
4 2
0 2 1
2 3 2

3 3
0 1 1
1 2 1
0 2 2
*/

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