oj.uz

Submission #1076732

# Submission time Handle Problem Language Result Execution time Memory
1076732 2024-08-26T16:02:07 Z NValchanov Colors (RMI18_colors) C++17
100 / 100
 459 ms 89408 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 30032 KB Output is correct
2 Correct 29 ms 29276 KB Output is correct
3 Correct 22 ms 29020 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 30316 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 30076 KB Output is correct
2 Correct 38 ms 29064 KB Output is correct
3 Correct 21 ms 28760 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 30076 KB Output is correct
2 Correct 38 ms 29064 KB Output is correct
3 Correct 21 ms 28760 KB Output is correct
4 Correct 112 ms 31740 KB Output is correct
5 Correct 288 ms 50756 KB Output is correct
6 Correct 459 ms 71368 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 30032 KB Output is correct
2 Correct 29 ms 29276 KB Output is correct
3 Correct 22 ms 29020 KB Output is correct
4 Correct 64 ms 30076 KB Output is correct
5 Correct 38 ms 29064 KB Output is correct
6 Correct 21 ms 28760 KB Output is correct
7 Correct 72 ms 30036 KB Output is correct
8 Correct 36 ms 29172 KB Output is correct
9 Correct 18 ms 28844 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 31632 KB Output is correct
2 Correct 234 ms 51400 KB Output is correct
3 Correct 237 ms 62320 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29532 KB Output is correct
2 Correct 20 ms 29364 KB Output is correct
3 Correct 16 ms 28760 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 30032 KB Output is correct
2 Correct 29 ms 29276 KB Output is correct
3 Correct 22 ms 29020 KB Output is correct
4 Correct 63 ms 30316 KB Output is correct
5 Correct 64 ms 30076 KB Output is correct
6 Correct 38 ms 29064 KB Output is correct
7 Correct 21 ms 28760 KB Output is correct
8 Correct 112 ms 31740 KB Output is correct
9 Correct 288 ms 50756 KB Output is correct
10 Correct 459 ms 71368 KB Output is correct
11 Correct 72 ms 30036 KB Output is correct
12 Correct 36 ms 29172 KB Output is correct
13 Correct 18 ms 28844 KB Output is correct
14 Correct 117 ms 31632 KB Output is correct
15 Correct 234 ms 51400 KB Output is correct
16 Correct 237 ms 62320 KB Output is correct
17 Correct 30 ms 29532 KB Output is correct
18 Correct 20 ms 29364 KB Output is correct
19 Correct 16 ms 28760 KB Output is correct
20 Correct 71 ms 31312 KB Output is correct
21 Correct 253 ms 54028 KB Output is correct
22 Correct 403 ms 89408 KB Output is correct