Submission #1015968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015968		boris_mihov	Colors (RMI18_colors)	C++17	100 / 100	643 ms	65144 KiB

colors

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 150000 + 10;
const int INF  = 1e9;

int n, m;
int c[MAXN];
int d[MAXN];
int perm[MAXN];
std::vector <int> g[MAXN];

struct DSU
{
    int par[MAXN];
    int min[MAXN];
    struct Roll
    {
        int *pos;
        int val;
        int t;
    };

    std::stack <Roll> st;
    int timer;

    void reset()
    {
        timer = 0;
        while (st.size()) st.pop();
        std::iota(par + 1, par + 1 + n, 1);
        for (int i = 1 ; i <= n ; ++i)
        {
            min[i] = c[i];
        }
    }

    int find(int node)
    {
        if (par[node] == node) return node;
        st.push({&par[node], par[node], timer}); timer++;
        return par[node] = find(par[node]);
    }

    void connect(int u, int v)
    {
        u = find(u);
        v = find(v);
        if (u == v)
        {
            return;
        }

        st.push({&par[u], par[u], timer});
        st.push({&min[v], min[v], timer});
        par[u] = v;
        min[v] = std::min(min[v], min[u]);
        timer++;
    }

    bool in(int u, int val)
    {
        return min[find(u)] == val;
    }

    void roll(int t)
    {
        while (st.size() && st.top().t >= t)
        {
            (*st.top().pos) = st.top().val;
            st.pop();
        }
    }
};

std::vector <int> byD[MAXN];
struct SegmentTree
{
    DSU dsu;
    bool in[MAXN];
    std::vector <int> tree[4 * MAXN];
    void build(int l, int r, int node)
    {
        tree[node].clear();
        if (l == r)
        {
            return;
        }

        int mid = l + r >> 1;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
    }

    void update(int l, int r, int node, int queryL, int queryR, int u)
    {
        if (queryL <= l && r <= queryR)
        {
            tree[node].push_back(u);
            return;
        }

        int mid = l + r >> 1;
        if (queryL <= mid) update(l, mid, 2*node, queryL, queryR, u);
        if (mid + 1 <= queryR) update(mid + 1, r, 2*node + 1, queryL, queryR, u);
    }

    bool solve(int l, int r, int node)
    {
        int t = dsu.timer;
        for (const int &u : tree[node])
        {
            in[u] = 1;
            for (const int &v : g[u])
            {
                if (in[v])
                {
                    dsu.connect(u, v);
                }
            }
        }

        bool result = true;
        if (l != r)
        {
            int mid = l + r >> 1;
            result &= solve(l, mid, 2*node);
            result &= solve(mid + 1, r, 2*node + 1);
        } else
        {
            for (const int &u : byD[l])
            {
                if (!dsu.in(u, l))
                {
                    result = false;
                    break;
                }
            }
        }

        dsu.roll(t);
        for (const int &u : tree[node])
        {
            in[u] = 0;
        }

        return result;
    }

    void build()
    {
        dsu.reset();
        std::fill(in + 1, in + 1 + n, false);
        build(1, n, 1);
    }

    void update(int l, int r, int u)
    {
        update(1, n, 1, l, r, u);
    }

    bool solve()
    {
        return solve(1, n, 1);
    }
};

SegmentTree tree;
void reset()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        g[i].clear();
        byD[i].clear();
    }
}

bool vis[MAXN];
void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        if (d[i] > c[i])
        {
            std::cout << 0 << '\n';
            return;
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        byD[d[i]].push_back(i); 
    }

    tree.build();
    for (int i = 1 ; i <= n ; ++i)
    {
        tree.update(d[i], c[i], i);
    }

    std::cout << tree.solve() << '\n';
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> c[i];
    }

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

    for (int i = 1 ; i <= m ; ++i)
    {   
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int tests;
int main()
{
    fastIOI();
    std::cin >> tests;

    while (tests--)
    {
        reset();
        input();
        solve();
    }

    return 0;
}

Compilation message (stderr)

colors.cpp: In member function 'void SegmentTree::build(int, int, int)':
colors.cpp:96:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         int mid = l + r >> 1;
      |                   ~~^~~
colors.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
colors.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = l + r >> 1;
      |                   ~~^~~
colors.cpp: In member function 'bool SegmentTree::solve(int, int, int)':
colors.cpp:132:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |             int mid = l + r >> 1;
      |                       ~~^~~

• 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