Submission #1296488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296488		cnam9	Colors (RMI18_colors)	C++20	0 / 100	86 ms	572 KiB

colors

#include <iostream>
#include <set>
#include <vector>
#include <cassert>

using namespace std;

constexpr int N = 1.5e5 + 5;

int n = 1;
int a[N];
int b[N];
vector<int> graph[N];
vector<int> witha[N];
vector<int> withb[N];
vector<int> tree[4 * N];

int parent[N];
int siez[N];

template <class ValueType, size_t N>
class BufferedStack {
    ValueType buf[N];
    ValueType *end = buf;

public:

    inline void clear() { end = buf; }
    inline bool empty() const { return end == buf; }

    inline ValueType top() const { return *end; }
    inline void pop() { --end; }
    inline void push(ValueType value) { *++end = value; }
};
BufferedStack<int, N> history;

inline int find_set(int u) {
    while (parent[u] != u) u = parent[u];
    return u;
}

inline void make_set(int u) {
    history.push(-u);
    parent[u] = u;
    siez[u] = 1;
}

inline bool is_set(int u) {
    return parent[u] != 0;
}

inline void union_sets(int u, int v) {
    u = find_set(u);
    v = find_set(v);

    if (u == v) return;

    if (siez[u] < siez[v]) swap(u, v);
    siez[u] += siez[v];
    parent[v] = u;
    history.push(v);
}

inline void undo() {
    int v = history.top();
    history.pop();
    if (v < 0) {
        parent[-v] = 0;
        return;
    }
    siez[parent[v]] -= siez[v];
    parent[v] = v;
}

int u, v, w;

void insert_recursive(int id, int l, int r) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) {
        tree[id].push_back(w);
        return;
    }
    int m = l + r >> 1;
    insert_recursive(id * 2, l, m);
    insert_recursive(id * 2 + 1, m + 1, r);
}

void insert(int l, int r, int x) {
    u = l, v = r, w = x;
    insert_recursive(1, 1, n);
}

bool good;

void clear(int id, int l, int r) {
    tree[id].clear();
    if (l < r) {
        int m = l + r >> 1;
        clear(id * 2, l, m);
        clear(id * 2 + 1, m + 1, r);
    }
}

void traverse(int id, int l, int r) {
    int checkpoint = history.top();

    for (int u : tree[id]) {
        make_set(u);
        for (int v : graph[u]) {
            if (!is_set(v)) continue;
            union_sets(u, v);
        }
    }
    if (l == r) {
        set<int> sources;
        for (int s : witha[l]) {
            sources.insert(find_set(s));
        }
        for (int t : withb[l]) {
            if (sources.find(find_set(t)) == sources.end()) {
                good = false;
                return;
            }
        }
    } else {
        int m = l + r >> 1;
        traverse(id * 2, l, m);
        if (!good) return;
        traverse(id * 2 + 1, m + 1, r);
        if (!good) return;
    }

    while (history.top() != checkpoint) {
        undo();
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt", "r", stdin);

int T;
cin >> T;

while (T--)
{
    clear(1, 1, n);
    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        witha[i].clear();
        withb[i].clear();
        parent[i] = 0;
    }

    int m;
    cin >> n >> m;
    fill(parent + 1, parent + n + 1, 0);

    for (int u = 1; u <= n; u++) { cin >> a[u]; }
    for (int u = 1; u <= n; u++) { cin >> b[u]; }

    while (m--) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for (int u = 1; u <= n; u++) {
        if (b[u] > a[u]) {
            cout << "0\n";
            continue;
        }
    }
    for (int u = 1; u <= n; u++) {
        insert(b[u], a[u], u);
        witha[a[u]].push_back(u);
        withb[b[u]].push_back(u);
    }
    history.clear();
    good = true;
    traverse(1, 1, n);

    cout << good << '\n';
}

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22