oj.uz

Submission #851828

# Submission time Handle Problem Language Result Execution time Memory
851828 2023-09-20T16:40:06 Z prvocislo Colors (RMI18_colors) C++17
78 / 100
 3000 ms 39504 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], ch[maxn];
struct dsu_rollback
{
    int cnt;
    dsu_rollback(int n)
    {
        for (int i = 0; i < n; i++) p[i] = i;
        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 (rand() & 1) swap(i, j);
        p[j] = i;
        ch[cnt++] = j;
    }
    void undo(int siz)
    {
        while (cnt > siz)
        {
            int v = ch[--cnt];
            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 89 ms 456 KB Output is correct
2 Correct 34 ms 344 KB Output is correct
3 Correct 16 ms 740 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 344 KB Output is correct
2 Correct 28 ms 344 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 173 ms 344 KB Output is correct
5 Correct 389 ms 14240 KB Output is correct
6 Correct 550 ms 39504 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 456 KB Output is correct
2 Correct 34 ms 344 KB Output is correct
3 Correct 16 ms 740 KB Output is correct
4 Correct 84 ms 344 KB Output is correct
5 Correct 28 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 99 ms 592 KB Output is correct
8 Correct 35 ms 344 KB Output is correct
9 Correct 6 ms 600 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 348 KB Output is correct
2 Correct 896 ms 14756 KB Output is correct
3 Correct 1676 ms 35580 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 344 KB Output is correct
2 Correct 12 ms 344 KB Output is correct
3 Correct 10 ms 348 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 456 KB Output is correct
2 Correct 34 ms 344 KB Output is correct
3 Correct 16 ms 740 KB Output is correct
4 Correct 60 ms 344 KB Output is correct
5 Correct 84 ms 344 KB Output is correct
6 Correct 28 ms 344 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 173 ms 344 KB Output is correct
9 Correct 389 ms 14240 KB Output is correct
10 Correct 550 ms 39504 KB Output is correct
11 Correct 99 ms 592 KB Output is correct
12 Correct 35 ms 344 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 188 ms 348 KB Output is correct
15 Correct 896 ms 14756 KB Output is correct
16 Correct 1676 ms 35580 KB Output is correct
17 Correct 31 ms 344 KB Output is correct
18 Correct 12 ms 344 KB Output is correct
19 Correct 10 ms 348 KB Output is correct
20 Correct 93 ms 604 KB Output is correct
21 Execution timed out 3024 ms 14924 KB Time limit exceeded
22 Halted 0 ms 0 KB -