oj.uz

Submission #851787

# Submission time Handle Problem Language Result Execution time Memory
851787 2023-09-20T15:40:50 Z prvocislo Colors (RMI18_colors) C++17
100 / 100
 532 ms 58388 KB 
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
using namespace std;

struct dsu_rollback
{
    vector<int> p, s, ch;
    dsu_rollback(int n)
    {
        p.resize(n), s.resize(n, 1);
        for (int i = 0; i < n; i++) p[i] = i;
    }
    int root(int i) { return p[i] == i ? i : root(p[i]); }
    void merge(int i, int j)
    {
        i = root(i), j = root(j);
        if (i == j) return;
        if (s[i] < s[j]) swap(i, j);
        p[j] = i, s[i] += s[j], ch.push_back(j);
    }
    void undo(int siz)
    {
        while (ch.size() > siz)
        {
            int v = ch.back(); ch.pop_back();
            s[p[v]] -= s[v], p[v] = v;
        }
    }
};
vector<int> ok, on;
vector<vector<int> > oa, ob, g; // vyskyty a-cok a vyskty b-cok
struct udaj
{
    int l, r, u;
};
bool dandc(int l, int r, vector<udaj> &v, dsu_rollback &d)
{
    int siz = d.ch.size();
    int m = (l + r) / 2;
    vector<udaj> v2;
    for (udaj u : v)
    {
        if (u.r < l || u.l > r) continue;
        if (u.l <= l && r <= u.r)
        {
            on[u.u] = 1;
            for (int i : g[u.u]) if (on[i]) d.merge(u.u, i);
            continue;
        }
        v2.push_back(u);
    }
    bool ans = true;
    if (l == r)
    {
        for (int x : oa[l]) ok[d.root(x)] = 1;
        for (int x : ob[l]) if (!ok[d.root(x)]) ans = false;
        for (int x : oa[l]) ok[d.root(x)] = 0;
    }
    else ans = dandc(l, m, v2, d) && dandc(m + 1, r, v2, d);
    for (udaj u : v) if (u.l <= l && r <= u.r) on[u.u] = 0;
    d.undo(siz);
    return ans;
}
int solve()
{
    int n, m;
    cin >> n >> m;
    oa.assign(n, {}), ob.assign(n, {}), g.assign(n, {}), ok.assign(n, 0), on.assign(n, 0);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i], oa[--a[i]].push_back(i);
    for (int i = 0; i < n; i++) cin >> b[i], ob[--b[i]].push_back(i);
    for (int i = 0, u, v; i < m; i++) cin >> u >> v, g[--u].push_back(--v), g[v].push_back(u);
    vector<udaj> v;
    for (int i = 0; i < n; i++)
    {
        if (a[i] < b[i]) return 0;
        v.push_back({ b[i], a[i], i });
    }
    dsu_rollback d(n);
    return dandc(0, n - 1, v, d);
}
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 member function 'void dsu_rollback::undo(int)':
colors.cpp:29:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |         while (ch.size() > siz)
      |                ~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 344 KB Output is correct
2 Correct 25 ms 348 KB Output is correct
3 Correct 3 ms 768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 344 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 468 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 3 ms 604 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 468 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 160 ms 748 KB Output is correct
5 Correct 353 ms 15044 KB Output is correct
6 Correct 532 ms 47496 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 344 KB Output is correct
2 Correct 25 ms 348 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 69 ms 468 KB Output is correct
5 Correct 24 ms 344 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 71 ms 476 KB Output is correct
8 Correct 24 ms 344 KB Output is correct
9 Correct 4 ms 600 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 740 KB Output is correct
2 Correct 298 ms 16292 KB Output is correct
3 Correct 348 ms 42004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 4 ms 600 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 344 KB Output is correct
2 Correct 25 ms 348 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 41 ms 344 KB Output is correct
5 Correct 69 ms 468 KB Output is correct
6 Correct 24 ms 344 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 160 ms 748 KB Output is correct
9 Correct 353 ms 15044 KB Output is correct
10 Correct 532 ms 47496 KB Output is correct
11 Correct 71 ms 476 KB Output is correct
12 Correct 24 ms 344 KB Output is correct
13 Correct 4 ms 600 KB Output is correct
14 Correct 132 ms 740 KB Output is correct
15 Correct 298 ms 16292 KB Output is correct
16 Correct 348 ms 42004 KB Output is correct
17 Correct 25 ms 344 KB Output is correct
18 Correct 7 ms 344 KB Output is correct
19 Correct 4 ms 600 KB Output is correct
20 Correct 60 ms 2896 KB Output is correct
21 Correct 284 ms 22264 KB Output is correct
22 Correct 441 ms 58388 KB Output is correct