oj.uz

Submission #1107593

# Submission time Handle Problem Language Result Execution time Memory
1107593 2024-11-01T16:20:08 Z cpptowin Colors (RMI18_colors) C++17
100 / 100
 480 ms 93696 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 200010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define bitcout(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    if (x >= mod)
        x -= mod;
}
struct event
{
    int u, szu, v, szv;
    event(int u, int szu, int v, int szv) : u(u), szu(szu), v(v), szv(szv){};
};
struct DSU
{
    vi par, sz;
    DSU(int n) : par(n), sz(n){};
    stack<event> st;
    void rollback(int x)
    {
        if (st.empty())
            return;
        while (st.size() > x)
        {
            auto top = st.top();
            st.pop();
            par[top.v] = top.v;
            sz[top.v] = top.szv;
            par[top.u] = top.u;
            sz[top.u] = top.szu;
        }
    }
    void make(int u)
    {
        par[u] = u;
        sz[u] = 1;
    }
    int find(int u)
    {
        return u == par[u] ? u : find(par[u]);
    }
    void Union(int u, int v)
    {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        if (sz[u] < sz[v])
            swap(u, v);
        st.push(event(u, sz[u], v, sz[v]));
        sz[u] += sz[v];
        par[v] = u;
    }
} g(maxn);
vii st[4 * maxn];
void up(int id, int l, int r, int u, int v, pii edge)
{
    if (u > r || l > v)
        return;
    if (u <= l and r <= v)
    {
        st[id].pb(edge);
        return;
    }
    int mid = l + r >> 1;
    up(id << 1, l, mid, u, v, edge);
    up(id << 1 | 1, mid + 1, r, u, v, edge);
}
int n, m, a[maxn], b[maxn];
vi ca[maxn], cb[maxn];
bool ok;
void dfs(int id, int l, int r)
{
    int timer = ss(g.st);
    for (auto [u, v] : st[id])
        g.Union(u, v);
    if (l == r)
    {
        unordered_set<int> st;
        for (int it : ca[l])
            st.insert(g.find(it));
        for (int it : cb[l])
            if (!st.count(g.find(it)))
                ok = 0;
    }
    else
    {
        int mid = l + r >> 1;
        dfs(id << 1, l, mid);
        dfs(id << 1 | 1, mid + 1, r);
    }
    g.rollback(timer);
}
void solve()
{
    ok = 1;
    cin >> n >> m;
    while(ss(g.st)) g.st.pop();
    fo(i, 1, n) g.make(i);
    fo(i, 1, 4 * n + 5) st[i].clear();
    fo(i, 1, n) ca[i].clear(), cb[i].clear();
    fo(i, 1, n) cin >> a[i], ca[a[i]].pb(i);
    fo(i, 1, n) cin >> b[i], cb[b[i]].pb(i);
    fo(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        int l = max(b[u], b[v]);
        int r = min(a[u], a[v]);
        if(l <= r)
        up(1, 1, n, l, r, {u, v});
    }
    fo(i, 1, n) 
    {
        if(a[i] < b[i]) 
        {
            cout << 0;en;
            return;
        }
    }
    dfs(1, 1, n);
    cout << ok;
    en;
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--)
        solve();
}

Compilation message

colors.cpp: In member function 'void DSU::rollback(int)':
colors.cpp:64:26: warning: comparison of integer expressions of different signedness: 'std::stack<event>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |         while (st.size() > x)
      |                ~~~~~~~~~~^~~
colors.cpp: In function 'void up(int, int, int, int, int, std::pair<int, int>)':
colors.cpp:106:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = l + r >> 1;
      |               ~~^~~
colors.cpp: In function 'void dfs(int, int, int)':
colors.cpp:129:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  129 |         int mid = l + r >> 1;
      |                   ~~^~~
colors.cpp: At global scope:
colors.cpp:166:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  166 | main()
      | ^~~~
colors.cpp: In function 'int main()':
colors.cpp:171:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
colors.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33208 KB Output is correct
2 Correct 23 ms 32336 KB Output is correct
3 Correct 10 ms 32048 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33000 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 31568 KB Output is correct
2 Correct 27 ms 32336 KB Output is correct
3 Correct 10 ms 32080 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 31568 KB Output is correct
2 Correct 27 ms 32336 KB Output is correct
3 Correct 10 ms 32080 KB Output is correct
4 Correct 127 ms 34888 KB Output is correct
5 Correct 289 ms 52692 KB Output is correct
6 Correct 447 ms 71760 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33208 KB Output is correct
2 Correct 23 ms 32336 KB Output is correct
3 Correct 10 ms 32048 KB Output is correct
4 Correct 96 ms 31568 KB Output is correct
5 Correct 27 ms 32336 KB Output is correct
6 Correct 10 ms 32080 KB Output is correct
7 Correct 56 ms 33192 KB Output is correct
8 Correct 34 ms 32336 KB Output is correct
9 Correct 10 ms 32092 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 34344 KB Output is correct
2 Correct 265 ms 53420 KB Output is correct
3 Correct 311 ms 62004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32080 KB Output is correct
2 Correct 15 ms 32468 KB Output is correct
3 Correct 12 ms 32080 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33208 KB Output is correct
2 Correct 23 ms 32336 KB Output is correct
3 Correct 10 ms 32048 KB Output is correct
4 Correct 47 ms 33000 KB Output is correct
5 Correct 96 ms 31568 KB Output is correct
6 Correct 27 ms 32336 KB Output is correct
7 Correct 10 ms 32080 KB Output is correct
8 Correct 127 ms 34888 KB Output is correct
9 Correct 289 ms 52692 KB Output is correct
10 Correct 447 ms 71760 KB Output is correct
11 Correct 56 ms 33192 KB Output is correct
12 Correct 34 ms 32336 KB Output is correct
13 Correct 10 ms 32092 KB Output is correct
14 Correct 105 ms 34344 KB Output is correct
15 Correct 265 ms 53420 KB Output is correct
16 Correct 311 ms 62004 KB Output is correct
17 Correct 27 ms 32080 KB Output is correct
18 Correct 15 ms 32468 KB Output is correct
19 Correct 12 ms 32080 KB Output is correct
20 Correct 68 ms 34376 KB Output is correct
21 Correct 250 ms 55812 KB Output is correct
22 Correct 480 ms 93696 KB Output is correct