oj.uz

Submission #948144

# Submission time Handle Problem Language Result Execution time Memory
948144 2024-03-17T16:32:40 Z Blagoj Colors (RMI18_colors) C++17
100 / 100
 484 ms 90616 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 2e5;

vector<int> a(mxn), b(mxn), cntA[mxn], cntB[mxn], ldr(mxn), rnk(mxn);
vector<pair<int, int>> edges, sgt[4 * mxn];

struct State {
    int x, y, xSize, ySize;
};

stack<State> s;

void clear(int n) {
    edges.clear();
    for (int i = 1; i <= n; i++) {
        cntA[i].clear();
        cntB[i].clear();
    }
    for (int i = 1; i <= 4 * n; i++) sgt[i].clear();  
}

void update(int k, int l, int r, int i, int j, pair<int, int> x) {
    if (l > j || r < i) return;
    if (i <= l && r <= j) {
        sgt[k].push_back(x);
        return;
    }
    int mid = (l + r) / 2;
    update(k * 2, l, mid, i, j, x);
    update(k * 2 + 1, mid + 1, r, i, j, x);
}

int Find(int x) {
    if (x == ldr[x]) return x;
    else return Find(ldr[x]);
}

void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) swap(x, y);
    s.push({x, y, rnk[x], rnk[y]});
    ldr[y] = x;
    rnk[x] += rnk[y];
}

void rollback(int sz) {
    while (s.size() > sz) {
        State top = s.top();
        s.pop();
        ldr[top.x] = top.x;
        ldr[top.y] = top.y;
        rnk[top.x] = top.xSize;
        rnk[top.y] = top.ySize;
    }
}

bool flag;

void solve(int k, int l, int r) {
    int sz = s.size();
    for (auto [f, t] : sgt[k]) Union(f, t);
    if (l == r) {
        unordered_set<int> cnt;
        for (auto x : cntA[l]) cnt.insert(Find(x));
        for (auto x : cntB[l]) {
            if (!cnt.count(Find(x))) flag = 0;
        }
    }
    else {
        int mid = (l + r) / 2;
        solve(k * 2, l, mid);
        solve(k * 2 + 1, mid + 1, r);
    }
    rollback(sz);
}

void testCase() {
    int n, m;
    cin >> n >> m;
    clear(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cntA[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        cntB[b[i]].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        edges.push_back({f, t});
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] < b[i]) {
            cout << 0 << endl;
            return;
        }
    }
    for (auto [f, t] : edges) {
        int mn = max(b[f], b[t]);
        int mx = min(a[f], a[t]);
        if (mn <= mx) update(1, 1, n, mn, mx, {f, t});
    }
    flag = 1;
    solve(1, 1, n);
    cout << flag << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 1; i < mxn; i++) {
        ldr[i] = i;
        rnk[i] = 1;
    }
    int t;
    cin >> t;
    while (t--) {
        testCase();
    }
}

Compilation message

colors.cpp: In function 'void rollback(int)':
colors.cpp:55:21: warning: comparison of integer expressions of different signedness: 'std::stack<State>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     while (s.size() > sz) {
      |            ~~~~~~~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 31580 KB Output is correct
2 Correct 32 ms 32080 KB Output is correct
3 Correct 12 ms 32092 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31952 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 31580 KB Output is correct
2 Correct 34 ms 32344 KB Output is correct
3 Correct 11 ms 31836 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 31580 KB Output is correct
2 Correct 34 ms 32344 KB Output is correct
3 Correct 11 ms 31836 KB Output is correct
4 Correct 159 ms 34900 KB Output is correct
5 Correct 322 ms 53328 KB Output is correct
6 Correct 464 ms 73220 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 31580 KB Output is correct
2 Correct 32 ms 32080 KB Output is correct
3 Correct 12 ms 32092 KB Output is correct
4 Correct 81 ms 31580 KB Output is correct
5 Correct 34 ms 32344 KB Output is correct
6 Correct 11 ms 31836 KB Output is correct
7 Correct 79 ms 33108 KB Output is correct
8 Correct 34 ms 32340 KB Output is correct
9 Correct 12 ms 32092 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 31832 KB Output is correct
2 Correct 373 ms 54048 KB Output is correct
3 Correct 314 ms 63172 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31836 KB Output is correct
2 Correct 17 ms 32092 KB Output is correct
3 Correct 13 ms 32000 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 31580 KB Output is correct
2 Correct 32 ms 32080 KB Output is correct
3 Correct 12 ms 32092 KB Output is correct
4 Correct 57 ms 31952 KB Output is correct
5 Correct 81 ms 31580 KB Output is correct
6 Correct 34 ms 32344 KB Output is correct
7 Correct 11 ms 31836 KB Output is correct
8 Correct 159 ms 34900 KB Output is correct
9 Correct 322 ms 53328 KB Output is correct
10 Correct 464 ms 73220 KB Output is correct
11 Correct 79 ms 33108 KB Output is correct
12 Correct 34 ms 32340 KB Output is correct
13 Correct 12 ms 32092 KB Output is correct
14 Correct 161 ms 31832 KB Output is correct
15 Correct 373 ms 54048 KB Output is correct
16 Correct 314 ms 63172 KB Output is correct
17 Correct 30 ms 31836 KB Output is correct
18 Correct 17 ms 32092 KB Output is correct
19 Correct 13 ms 32000 KB Output is correct
20 Correct 75 ms 34356 KB Output is correct
21 Correct 320 ms 56844 KB Output is correct
22 Correct 484 ms 90616 KB Output is correct