oj.uz

Submission #856494

# Submission time Handle Problem Language Result Execution time Memory
856494 2023-10-03T17:26:08 Z borisAngelov Colors (RMI18_colors) C++17
100 / 100
 511 ms 83004 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 150005;

int n, m;

int a[maxn];
int b[maxn];

vector<int> g[maxn];
bool seen[maxn];

vector<int> byAValues[maxn];
vector<int> byBValues[maxn];

struct DSU
{
    struct Roll
    {
        int *pos;
        int val;
        int t;
    };

    int time;
    int par[maxn];
    int dep[maxn];
    stack<Roll> rollback;

    void build(int n)
    {
        time = 1;

        for (int i = 1; i <= n; ++i)
        {
            par[i] = i;
            dep[i] = 1;
        }

        while (!rollback.empty())
        {
            rollback.pop();
        }
    }

    int root(int x)
    {
        if (x == par[x])
        {
            return x;
        }

        rollback.push({&par[x], par[x], time});

        return par[x] = root(par[x]);
    }

    void connect(int x, int y)
    {
        x = root(x);
        y = root(y);

        if (x == y)
        {
            return;
        }

        ++time;

        if (dep[x] > dep[y])
        {
            swap(x, y);
        }

        rollback.push({&par[x], par[x], time});
        par[x] = y;

        if (dep[x] == dep[y])
        {
            rollback.push({&dep[y], dep[y], time});
            ++dep[y];
        }
    }

    void makeRollback(int to)
    {
        time = to;

        while (!rollback.empty() && rollback.top().t > time)
        {
            *rollback.top().pos = rollback.top().val;
            rollback.pop();
        }
    }
};

DSU dsu;

struct edge
{
    int x;
    int y;

    edge()
    {

    }

    edge(int _x, int _y)
    {
        x = _x;
        y = _y;
    }
};

bool isPossible = true;

int seenRoot[maxn];
int timestamp = 0;

struct DynamicConnectivity
{
    vector<edge> tree[4 * maxn];

    void build(int n)
    {
        timestamp = 0;

        for (int i = 1; i <= 4 * n; ++i)
        {
            if (i <= n)
            {
                seenRoot[i] = 0;
            }

            tree[i].clear();
        }
    }

    void addEdge(int node, int l, int r, int from, int to, edge e)
    {
        if (from <= l && r <= to)
        {
            //cout << "put edge on [" << l << ", " << r << "]" << endl;
            tree[node].push_back(e);
            return;
        }

        int mid = (l + r) / 2;

        if (from <= mid)
        {
            addEdge(2 * node, l, mid, from, to, e);
        }

        if (to >= mid + 1)
        {
            addEdge(2 * node + 1, mid + 1, r, from, to, e);
        }
    }

    void divideAndConquer(int node, int l, int r)
    {
        int rollbackTime = dsu.time;

        for (int i = 0; i < tree[node].size(); ++i)
        {
            dsu.connect(tree[node][i].x, tree[node][i].y);
        }

        if (l == r)
        {
            ++timestamp;

            for (int i = 0; i < byAValues[l].size(); ++i)
            {
                //cout << "seen " << byAValues[l][i] << " :: " << dsu.root(byAValues[l][i]) << " on " << timestamp << endl;
                //cout << dsu.root(byAValues[l][i]) << endl;
                seenRoot[dsu.root(byAValues[l][i])] = timestamp;
            }

            for (int i = 0; i < byBValues[l].size(); ++i)
            {
                //cout << "now " << dsu.root(byBValues[l][i]) << ' ' << seen[dsu.root(byBValues[l][i])] << endl;
                if (seenRoot[dsu.root(byBValues[l][i])] != timestamp)
                {
                    //cout << "oh" << endl;
                    isPossible = false;
                }
            }
        }
        else
        {
            int mid = (l + r) / 2;
            divideAndConquer(2 * node, l, mid);
            divideAndConquer(2 * node + 1, mid + 1, r);
        }

        dsu.makeRollback(rollbackTime);
    }

    void addEdge(int from, int to, edge e)
    {
        addEdge(1, 1, n, from, to, e);
    }
};

DynamicConnectivity dynCon;

void reset()
{
    for (int i = 1; i <= n; ++i)
    {
        seen[i] = false;
        g[i].clear();
        byAValues[i].clear();
        byBValues[i].clear();
    }
}

void read()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        cin >> b[i];
    }
}

bool hasOutput = false;

void checkTrivialCases()
{
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] < b[i])
        {
            hasOutput = true;
            return;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        seen[a[i]] = true;
    }

    for (int i = 1; i <= m; ++i)
    {
        if (seen[b[i]] == false)
        {
            hasOutput = true;
            return;
        }
    }
}

void solve()
{
    hasOutput = false;
    //checkTrivialCases();

    for (int i = 1; i <= n; ++i)
    {
        byAValues[a[i]].push_back(i);
        byBValues[b[i]].push_back(i);
    }

    dsu.build(n);
    dynCon.build(n);

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;

        int from = max(b[x], b[y]);
        int to = min(a[x], a[y]);

        if (from <= to && hasOutput == false)
        {
            //cout << "add " << x << " to " << y << " in [" << from << ", " << to << "]" << endl;
            dynCon.addEdge(from, to, edge(x, y));
        }
    }

    if (hasOutput == true)
    {
        cout << "0\n";
        return;
    }

    if (n == 1)
    {
        cout << "1\n";
        return;
    }

    isPossible = true;
    dynCon.divideAndConquer(1, 1, n);

    if (isPossible == true)
    {
        cout << "1\n";
    }
    else
    {
        cout << "0\n";
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    int q;
    cin >> q;

    while (q--)
    {
        reset();
        read();
        solve();
    }

    return 0;
}

/*
1
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2

add 1 to 2 in [2, 3]
add 2 to 3 in [2, 2]
add 4 to 2 in [1, 1]
*/

Compilation message

colors.cpp: In member function 'void DynamicConnectivity::divideAndConquer(int, int, int)':
colors.cpp:168:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         for (int i = 0; i < tree[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~
colors.cpp:177:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |             for (int i = 0; i < byAValues[l].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~
colors.cpp:184:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |             for (int i = 0; i < byBValues[l].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 27228 KB Output is correct
2 Correct 21 ms 27228 KB Output is correct
3 Correct 7 ms 27484 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 27496 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 27336 KB Output is correct
2 Correct 25 ms 27480 KB Output is correct
3 Correct 8 ms 27484 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 27336 KB Output is correct
2 Correct 25 ms 27480 KB Output is correct
3 Correct 8 ms 27484 KB Output is correct
4 Correct 121 ms 27352 KB Output is correct
5 Correct 331 ms 42880 KB Output is correct
6 Correct 511 ms 63164 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 27228 KB Output is correct
2 Correct 21 ms 27228 KB Output is correct
3 Correct 7 ms 27484 KB Output is correct
4 Correct 62 ms 27336 KB Output is correct
5 Correct 25 ms 27480 KB Output is correct
6 Correct 8 ms 27484 KB Output is correct
7 Correct 55 ms 27228 KB Output is correct
8 Correct 25 ms 27380 KB Output is correct
9 Correct 8 ms 27484 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 27360 KB Output is correct
2 Correct 304 ms 45072 KB Output is correct
3 Correct 266 ms 51952 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27416 KB Output is correct
2 Correct 17 ms 27996 KB Output is correct
3 Correct 10 ms 27480 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 27228 KB Output is correct
2 Correct 21 ms 27228 KB Output is correct
3 Correct 7 ms 27484 KB Output is correct
4 Correct 56 ms 27496 KB Output is correct
5 Correct 62 ms 27336 KB Output is correct
6 Correct 25 ms 27480 KB Output is correct
7 Correct 8 ms 27484 KB Output is correct
8 Correct 121 ms 27352 KB Output is correct
9 Correct 331 ms 42880 KB Output is correct
10 Correct 511 ms 63164 KB Output is correct
11 Correct 55 ms 27228 KB Output is correct
12 Correct 25 ms 27380 KB Output is correct
13 Correct 8 ms 27484 KB Output is correct
14 Correct 105 ms 27360 KB Output is correct
15 Correct 304 ms 45072 KB Output is correct
16 Correct 266 ms 51952 KB Output is correct
17 Correct 32 ms 27416 KB Output is correct
18 Correct 17 ms 27996 KB Output is correct
19 Correct 10 ms 27480 KB Output is correct
20 Correct 79 ms 29900 KB Output is correct
21 Correct 292 ms 53204 KB Output is correct
22 Correct 510 ms 83004 KB Output is correct