lessons/参考实现/07-二分图/CodeForces-1634E.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int arrays;
    cin >> arrays;
    vector<vector<long long>> input(arrays);
    vector<long long> all_values;
    int edge_count = 0;
    for (int i = 0; i < arrays; ++i) {
        int length;
        cin >> length;
        input[i].resize(length);
        for (long long &x : input[i]) {
            cin >> x;
            all_values.push_back(x);
        }
        edge_count += length;
    }
    sort(all_values.begin(), all_values.end());
    all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());
    int value_count = static_cast<int>(all_values.size());
    vector<vector<pair<int, int>>> graph(arrays + value_count);
    vector<pair<int, int>> location(edge_count);
    vector<int> value_degree(value_count, 0);
    int edge = 0;
    for (int i = 0; i < arrays; ++i) {
        for (int j = 0; j < static_cast<int>(input[i].size()); ++j) {
            int value = lower_bound(all_values.begin(), all_values.end(), input[i][j]) - all_values.begin();
            int node = arrays + value;
            graph[i].push_back({node, edge});
            graph[node].push_back({i, edge});
            location[edge] = {i, j};
            ++value_degree[value];
            ++edge;
        }
    }
    for (int degree : value_degree) {
        if (degree & 1) {
            cout << "NO\n";
            return 0;
        }
    }

    vector<string> answer(arrays);
    for (int i = 0; i < arrays; ++i) answer[i].assign(input[i].size(), '?');
    vector<int> iterator(graph.size(), 0);
    vector<char> used(edge_count, false);
    for (int source = 0; source < static_cast<int>(graph.size()); ++source) {
        if (iterator[source] == static_cast<int>(graph[source].size())) continue;
        vector<int> stack{source};
        while (!stack.empty()) {
            int v = stack.back();
            while (iterator[v] < static_cast<int>(graph[v].size())
                   && used[graph[v][iterator[v]].second]) ++iterator[v];
            if (iterator[v] == static_cast<int>(graph[v].size())) {
                stack.pop_back();
                continue;
            }
            auto [to, id] = graph[v][iterator[v]++];
            if (used[id]) continue;
            used[id] = true;
            auto [array, position] = location[id];
            answer[array][position] = (v < arrays ? 'L' : 'R');
            stack.push_back(to);
        }
    }
    cout << "YES\n";
    for (const string &line : answer) cout << line << '\n';
    return 0;
}