Submission #856494

#	Time	Username	Problem	Language	Result	Execution time	Memory
856494		borisAngelov	Colors (RMI18_colors)	C++17	100 / 100	511 ms	83004 KiB

colors

#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 (stderr)

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 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22