oj.uz

Submission #443275

# Submission time Handle Problem Language Result Execution time Memory
443275 2021-07-10T09:22:26 Z valerikk Colors (RMI18_colors) C++17
100 / 100
 802 ms 75876 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 17996 KB Output is correct
2 Correct 40 ms 18060 KB Output is correct
3 Correct 16 ms 18292 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 18136 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 17992 KB Output is correct
2 Correct 40 ms 17920 KB Output is correct
3 Correct 16 ms 18180 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 17992 KB Output is correct
2 Correct 40 ms 17920 KB Output is correct
3 Correct 16 ms 18180 KB Output is correct
4 Correct 173 ms 18004 KB Output is correct
5 Correct 444 ms 37344 KB Output is correct
6 Correct 802 ms 59536 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 17996 KB Output is correct
2 Correct 40 ms 18060 KB Output is correct
3 Correct 16 ms 18292 KB Output is correct
4 Correct 101 ms 17992 KB Output is correct
5 Correct 40 ms 17920 KB Output is correct
6 Correct 16 ms 18180 KB Output is correct
7 Correct 85 ms 17996 KB Output is correct
8 Correct 39 ms 17996 KB Output is correct
9 Correct 16 ms 18124 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 18200 KB Output is correct
2 Correct 474 ms 39976 KB Output is correct
3 Correct 466 ms 48316 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17996 KB Output is correct
2 Correct 25 ms 18324 KB Output is correct
3 Correct 18 ms 18124 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 17996 KB Output is correct
2 Correct 40 ms 18060 KB Output is correct
3 Correct 16 ms 18292 KB Output is correct
4 Correct 83 ms 18136 KB Output is correct
5 Correct 101 ms 17992 KB Output is correct
6 Correct 40 ms 17920 KB Output is correct
7 Correct 16 ms 18180 KB Output is correct
8 Correct 173 ms 18004 KB Output is correct
9 Correct 444 ms 37344 KB Output is correct
10 Correct 802 ms 59536 KB Output is correct
11 Correct 85 ms 17996 KB Output is correct
12 Correct 39 ms 17996 KB Output is correct
13 Correct 16 ms 18124 KB Output is correct
14 Correct 162 ms 18200 KB Output is correct
15 Correct 474 ms 39976 KB Output is correct
16 Correct 466 ms 48316 KB Output is correct
17 Correct 48 ms 17996 KB Output is correct
18 Correct 25 ms 18324 KB Output is correct
19 Correct 18 ms 18124 KB Output is correct
20 Correct 117 ms 20640 KB Output is correct
21 Correct 427 ms 43712 KB Output is correct
22 Correct 798 ms 75876 KB Output is correct