Submission #1076732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076732		NValchanov	Colors (RMI18_colors)	C++17	100 / 100	459 ms	89408 KiB

colors

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int MAXM = 2e5 + 10;

int has[MAXN];
int wants[MAXN];

vector < int > have_color[MAXN];
vector < int > want_color[MAXN];

struct edge
{
    int u, v;

    edge()
    {
        u = 1;
        v = 1;
    }

    edge(int _u, int _v)
    {
        if(_u > _v)
            swap(_u, _v);

        u = _u;
        v = _v;
    }

    friend bool operator<(edge e1, edge e2)
    {
        if(e1.u != e2.u)
            return e1.u < e2.u;

        return e1.v < e2.v;
    }
};

vector < edge > edges;

struct SegmentTree
{
    struct DSU
    {
        int n, sz;
        int leader[MAXN];
        int sizes[MAXN];
        stack < int > st;

        void init(int _n)
        {
            n = _n;
            sz = 0;

            while(!st.empty())
                st.pop();

            for(int i = 1; i <= n; i++)
            {
                leader[i] = i;
                sizes[i] = 1;
            }
        }

        int size()
        {
            return sz;
        }

        int find_leader(int u)
        {
            return leader[u] == u ? u : find_leader(leader[u]);
        }

        bool connected(int u, int v)
        {
            return find_leader(u) == find_leader(v);
        }

        void unite(int u, int v)
        {
            u = find_leader(u);
            v = find_leader(v);

            if(u == v)
                return;

            if(sizes[u] < sizes[v])
                swap(u, v);

            sizes[u] += sizes[v];
            leader[v] = u;
            
            n--;
            sz++;

            st.push(v);
        }

        void rollback(int t)
        {
            while(st.size() > t)
            {
                int u = st.top();
                st.pop();

                n++;
                sz--;

                sizes[leader[u]] -= sizes[u];
                leader[u] = u;
            }
        }
    };

    int n, m;
    DSU dsu;

    vector < edge > tree[4 * MAXN];
    bool can[MAXN];

    void clear(int left, int right, int idx)
    {
        tree[idx].clear();

        if(left == right)
            return;

        int mid = left + (right - left) / 2;

        clear(left, mid, 2 * idx);
        clear(mid + 1, right, 2 * idx + 1);
    }

    void init(int _n, int _m)
    {
        n = _n;
        m = _m;

        dsu.init(n);

        for(int i = 1; i <= n; i++)
        {
            can[i] = false;
        }

        clear(0, m, 1);
    }

    void update(int left, int right, int idx, int qleft, int qright, edge e)
    {
        if(qleft > qright)
            return;

        if(left > qright || right < qleft)
            return;

        if(qleft <= left && right <= qright)
        {
            tree[idx].push_back(e);
            return;
        }

        int mid = left + (right - left) / 2;

        update(left, mid, 2 * idx, qleft, qright, e);
        update(mid + 1, right, 2 * idx + 1, qleft, qright, e);
    }

    void calc(int left, int right, int idx)
    {
        int t = dsu.size();

        for(edge e : tree[idx])
        {
            dsu.unite(e.u, e.v);
        }

        if(left == right)
        {
            set < int > sources;

            for(int u : have_color[left])
            {
                sources.insert(dsu.find_leader(u));
            }

            for(int u : want_color[left])
            {
                if(sources.find(dsu.find_leader(u)) != sources.end())
                {
                    can[u] = true;
                }
            }

            dsu.rollback(t);

            return;
        }

        int mid = left + (right - left) / 2;

        calc(left, mid, 2 * idx);
        calc(mid + 1, right, 2 * idx + 1);

        dsu.rollback(t);
    }

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

    void calc()
    {
        calc(1, n, 1);
    }

    bool query(int t)
    {
        return can[t];
    }
};

int n, m;
SegmentTree st;

void init()
{
    st.init(n, m);

    for(int i = 1; i <= n; i++)
    {
        have_color[i].clear();
        want_color[i].clear();
    }
    
    edges.clear();
}

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

    init();

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

        have_color[has[i]].push_back(i);
    }

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

        want_color[wants[i]].push_back(i);
    }

    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;

        edges.push_back(edge(u, v));
    }
}

void solve()
{
    for(edge e : edges)
    {
        int from = max(wants[e.u], wants[e.v]);
        int to = min(has[e.u], has[e.v]);

        st.update(from, to, e);
    }

    st.calc();
}

void find_ans()
{
    bool ans = true;

    for(int i = 1; i <= n; i++)
    {
        ans &= st.query(i);
    }

    cout << ans << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;

    while(t--)
    {
        read();
        solve();
        find_ans();
    }

    return 0;
}

Compilation message (stderr)

colors.cpp: In member function 'void SegmentTree::DSU::rollback(int)':
colors.cpp:109:29: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |             while(st.size() > t)
      |                   ~~~~~~~~~~^~~

• 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