oj.uz

Submission #851826

# Submission time Handle Problem Language Result Execution time Memory
851826 2023-09-20T16:38:41 Z prvocislo Colors (RMI18_colors) C++17
100 / 100
 501 ms 51904 KB 
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
using namespace std;

const int maxn = 15e4+5;
int p[maxn], s[maxn], ch[maxn];
struct dsu_rollback
{
    int cnt;
    dsu_rollback(int n)
    {
        for (int i = 0; i < n; i++) p[i] = i, s[i] = 1;
        cnt = 0;
    }
    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[cnt++] = j;
    }
    void undo(int siz)
    {
        while (cnt > siz)
        {
            int v = ch[--cnt];
            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.cnt;
    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;
    scanf("%d%d", &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++) scanf("%d", &a[i]), oa[--a[i]].push_back(i);
    for (int i = 0; i < n; i++) scanf("%d", &b[i]), ob[--b[i]].push_back(i);
    for (int i = 0, u, v; i < m; i++) scanf("%d%d", &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()
{
    int t;
    scanf("%d", &t);
    while (t--) printf("%d\n", solve());
    return 0;
}

Compilation message

colors.cpp: In function 'int solve()':
colors.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:79:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     for (int i = 0; i < n; i++) scanf("%d", &a[i]), oa[--a[i]].push_back(i);
      |                                 ~~~~~^~~~~~~~~~~~~
colors.cpp:80:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     for (int i = 0; i < n; i++) scanf("%d", &b[i]), ob[--b[i]].push_back(i);
      |                                 ~~~~~^~~~~~~~~~~~~
colors.cpp:81:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     for (int i = 0, u, v; i < m; i++) scanf("%d%d", &u, &v), g[--u].push_back(--v), g[v].push_back(u);
      |                                       ~~~~~^~~~~~~~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 344 KB Output is correct
2 Correct 26 ms 348 KB Output is correct
3 Correct 4 ms 740 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 484 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 468 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 4 ms 604 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 468 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 174 ms 492 KB Output is correct
5 Correct 364 ms 14396 KB Output is correct
6 Correct 501 ms 39988 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 344 KB Output is correct
2 Correct 26 ms 348 KB Output is correct
3 Correct 4 ms 740 KB Output is correct
4 Correct 84 ms 468 KB Output is correct
5 Correct 27 ms 344 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 83 ms 344 KB Output is correct
8 Correct 28 ms 348 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 159 ms 492 KB Output is correct
2 Correct 342 ms 14812 KB Output is correct
3 Correct 368 ms 36408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 344 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 5 ms 344 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 344 KB Output is correct
2 Correct 26 ms 348 KB Output is correct
3 Correct 4 ms 740 KB Output is correct
4 Correct 55 ms 484 KB Output is correct
5 Correct 84 ms 468 KB Output is correct
6 Correct 27 ms 344 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 174 ms 492 KB Output is correct
9 Correct 364 ms 14396 KB Output is correct
10 Correct 501 ms 39988 KB Output is correct
11 Correct 83 ms 344 KB Output is correct
12 Correct 28 ms 348 KB Output is correct
13 Correct 4 ms 600 KB Output is correct
14 Correct 159 ms 492 KB Output is correct
15 Correct 342 ms 14812 KB Output is correct
16 Correct 368 ms 36408 KB Output is correct
17 Correct 34 ms 344 KB Output is correct
18 Correct 9 ms 348 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 78 ms 344 KB Output is correct
21 Correct 318 ms 17560 KB Output is correct
22 Correct 467 ms 51904 KB Output is correct