Submission #443275

#	Time	Username	Problem	Language	Result	Execution time	Memory
443275		valerikk	Colors (RMI18_colors)	C++17	100 / 100	802 ms	75876 KiB

colors

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

const int N = 1.5e5 + 123;

int n, m;
int a[N], b[N];
vector<pair<int, int>> t[4 * N];
int p[N], sz[N], mn[N];
vector<pair<int*, int>> st;
vector<int> by_b[N];
int ans;

int get(int v) {
    while (v != p[v]) v = p[v];
    return v;
}

void merge(int v, int u) {
    v = get(v), u = get(u);
    if (v != u) {
        if (sz[v] > sz[u]) swap(v, u);
        st.push_back({&sz[u], sz[u]});
        st.push_back({&mn[u], mn[u]});
        st.push_back({&p[v], p[v]});
        sz[u] += sz[v];
        mn[u] = min(mn[u], mn[v]);
        p[v] = u;
    }
}

void backup(int x) {
    while (st.size() > x) {
        auto pp = st.back();
        *pp.first = pp.second;
        st.pop_back();
    }
}

void add(int v, int l, int r, int x, int y, pair<int, int> pp) {
    if (l >= y || r <= x) return;
    if (l >= x && r <= y) {
        t[v].push_back(pp);
        return;
    }
    int mid = (l + r) / 2;
    add(2 * v, l, mid, x, y, pp);
    add(2 * v + 1, mid, r, x, y, pp);
}

void dfs(int v, int l, int r) {
    int x = st.size();
    for (auto pp : t[v]) merge(pp.first, pp.second);
    if (r - l == 1) {
        for (int i : by_b[l]) {
            if (mn[get(i)] != l) ans = 0;
        }
    } else {
        int mid = (l + r) / 2;
        dfs(2 * v, l, mid);
        dfs(2 * v + 1, mid, r);
    }
    backup(x);
}

int solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
    }
    for (int i = 0; i < n; i++) by_b[i].clear();
    for (int i = 0; i < 4 * n; i++) t[i].clear();
    while (m--) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        int l = max(b[v], b[u]), r = min(a[v], a[u]);
        if (l <= r) add(1, 0, n, l, r + 1, {v, u});
    }
    for (int i = 0; i < n; i++) {
        if (a[i] < b[i]) return 0;
    }
    for (int i = 0; i < n; i++) {
        p[i] = i;
        sz[i] = 1;
        mn[i] = a[i];
        by_b[b[i]].push_back(i);
    }
    ans = 1;
    dfs(1, 0, n);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cout << solve() << "\n";
    }
    return 0;
}

Compilation message (stderr)

colors.cpp: In function 'void backup(int)':
colors.cpp:34:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     while (st.size() > x) {
      |            ~~~~~~~~~~^~~

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