oj.uz

Submission #1015968

# Submission time Handle Problem Language Result Execution time Memory
1015968 2024-07-07T07:18:28 Z boris_mihov Colors (RMI18_colors) C++17
100 / 100
 643 ms 65144 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 53 ms 22928 KB Output is correct
2 Correct 26 ms 22048 KB Output is correct
3 Correct 12 ms 21852 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 23036 KB Output is correct
2 Correct 29 ms 22236 KB Output is correct
3 Correct 12 ms 21864 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 23036 KB Output is correct
2 Correct 29 ms 22236 KB Output is correct
3 Correct 12 ms 21864 KB Output is correct
4 Correct 118 ms 24660 KB Output is correct
5 Correct 340 ms 40512 KB Output is correct
6 Correct 527 ms 58900 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 22928 KB Output is correct
2 Correct 26 ms 22048 KB Output is correct
3 Correct 12 ms 21852 KB Output is correct
4 Correct 64 ms 23036 KB Output is correct
5 Correct 29 ms 22236 KB Output is correct
6 Correct 12 ms 21864 KB Output is correct
7 Correct 63 ms 22936 KB Output is correct
8 Correct 29 ms 22108 KB Output is correct
9 Correct 12 ms 21852 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 24656 KB Output is correct
2 Correct 320 ms 41796 KB Output is correct
3 Correct 346 ms 54700 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 22364 KB Output is correct
2 Correct 17 ms 22056 KB Output is correct
3 Correct 13 ms 21852 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 22928 KB Output is correct
2 Correct 26 ms 22048 KB Output is correct
3 Correct 12 ms 21852 KB Output is correct
4 Correct 63 ms 23380 KB Output is correct
5 Correct 64 ms 23036 KB Output is correct
6 Correct 29 ms 22236 KB Output is correct
7 Correct 12 ms 21864 KB Output is correct
8 Correct 118 ms 24660 KB Output is correct
9 Correct 340 ms 40512 KB Output is correct
10 Correct 527 ms 58900 KB Output is correct
11 Correct 63 ms 22936 KB Output is correct
12 Correct 29 ms 22108 KB Output is correct
13 Correct 12 ms 21852 KB Output is correct
14 Correct 109 ms 24656 KB Output is correct
15 Correct 320 ms 41796 KB Output is correct
16 Correct 346 ms 54700 KB Output is correct
17 Correct 29 ms 22364 KB Output is correct
18 Correct 17 ms 22056 KB Output is correct
19 Correct 13 ms 21852 KB Output is correct
20 Correct 66 ms 24148 KB Output is correct
21 Correct 387 ms 46296 KB Output is correct
22 Correct 643 ms 65144 KB Output is correct