oj.uz

Submission #445858

# Submission time Handle Problem Language Result Execution time Memory
445858 2021-07-19T23:28:54 Z JovanB Colors (RMI18_colors) C++17
100 / 100
 692 ms 82248 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;

int A[N+5];
int B[N+5];

struct DSU{
    int n;
    int par[N+5];
    int sz[N+5];
    struct operacija{
        int a, b, sza, szb;
    };
    stack <operacija> st;
    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) par[i] = i;
        for(int i=1; i<=n; i++) sz[i] = 1;
    }
    int root(int x){ return (x == par[x] ? x : root(par[x])); }
    void povezi(int a, int b){
        a = root(a);
        b = root(b);
        if(sz[a] < sz[b]) swap(a, b);
        st.push({a, b, sz[a], sz[b]});
        if(a == b) return;
        sz[a] += sz[b];
        par[b] = a;
    }
    void rollback(){
        int a = st.top().a;
        int b = st.top().b;
        sz[a] = st.top().sza;
        sz[b] = st.top().szb;
        par[b] = b;
        st.pop();
    }
};

vector <int> koji[N+5];
vector <int> treba[N+5];

vector <pair <int, int>> edges;
vector <pair <int, int>> zivi[4*N+5];

void klear(int n){
    for(int i=1; i<=n; i++) koji[A[i]].clear();
    for(int i=1; i<=n; i++) treba[B[i]].clear();
    for(int i=1; i<=4*n; i++) zivi[i].clear();
    edges.clear();
}

map <int, bool> ima;

void upd(int node, int l, int r, int tl, int tr, pair <int, int> edge){
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        zivi[node].push_back(edge);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, edge);
    upd(node*2+1, mid+1, r, tl, tr, edge);
}

DSU dsu;

bool dfs(int node, int l, int r){
    for(auto c : zivi[node]) dsu.povezi(c.first, c.second);
    if(l == r){
        bool svi = 1;
        ima.clear();
        for(auto c : koji[l]) ima[dsu.root(c)] = 1;
        for(auto c : treba[l]) svi &= ima[dsu.root(c)];
        for(auto c : zivi[node]) dsu.rollback();
        return svi;
    }
    int mid = (l+r)/2;
    bool moze = (dfs(node*2, l, mid));
    if(moze) moze &= dfs(node*2+1, mid+1, r);
    for(auto c : zivi[node]) dsu.rollback();
    return moze;
}

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> A[i];
    for(int i=1; i<=n; i++) cin >> B[i];
    for(int i=1; i<=n; i++) koji[A[i]].push_back(i);
    for(int i=1; i<=n; i++) treba[B[i]].push_back(i);
    for(int i=1; i<=m; i++){
        int a, b;
        cin >> a >> b;
        edges.push_back({a, b});
    }
    for(int i=1; i<=n; i++){
        if(A[i] < B[i]){
            cout << "0\n";
            klear(n);
            return;
        }
    }
    for(auto edge : edges){
        int a = edge.first;
        int b = edge.second;
        int l = max(B[a], B[b]);
        int r = min(A[a], A[b]);
        if(l <= r) upd(1, 1, n, l, r, {a, b});
    }
    dsu.init(n);
    if(dfs(1, 1, n)) cout << "1\n";
    else cout << "0\n";
    klear(n);
    return;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message

colors.cpp: In function 'bool dfs(int, int, int)':
colors.cpp:80:18: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   80 |         for(auto c : zivi[node]) dsu.rollback();
      |                  ^
colors.cpp:86:14: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   86 |     for(auto c : zivi[node]) dsu.rollback();
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28636 KB Output is correct
2 Correct 42 ms 28600 KB Output is correct
3 Correct 19 ms 28888 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 28736 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 28652 KB Output is correct
2 Correct 42 ms 28548 KB Output is correct
3 Correct 19 ms 28744 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 28652 KB Output is correct
2 Correct 42 ms 28548 KB Output is correct
3 Correct 19 ms 28744 KB Output is correct
4 Correct 199 ms 28540 KB Output is correct
5 Correct 418 ms 44532 KB Output is correct
6 Correct 692 ms 65396 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28636 KB Output is correct
2 Correct 42 ms 28600 KB Output is correct
3 Correct 19 ms 28888 KB Output is correct
4 Correct 92 ms 28652 KB Output is correct
5 Correct 42 ms 28548 KB Output is correct
6 Correct 19 ms 28744 KB Output is correct
7 Correct 89 ms 28544 KB Output is correct
8 Correct 43 ms 28580 KB Output is correct
9 Correct 20 ms 28800 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 28492 KB Output is correct
2 Correct 389 ms 45776 KB Output is correct
3 Correct 418 ms 55376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 28616 KB Output is correct
2 Correct 28 ms 28940 KB Output is correct
3 Correct 21 ms 28748 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28636 KB Output is correct
2 Correct 42 ms 28600 KB Output is correct
3 Correct 19 ms 28888 KB Output is correct
4 Correct 102 ms 28736 KB Output is correct
5 Correct 92 ms 28652 KB Output is correct
6 Correct 42 ms 28548 KB Output is correct
7 Correct 19 ms 28744 KB Output is correct
8 Correct 199 ms 28540 KB Output is correct
9 Correct 418 ms 44532 KB Output is correct
10 Correct 692 ms 65396 KB Output is correct
11 Correct 89 ms 28544 KB Output is correct
12 Correct 43 ms 28580 KB Output is correct
13 Correct 20 ms 28800 KB Output is correct
14 Correct 168 ms 28492 KB Output is correct
15 Correct 389 ms 45776 KB Output is correct
16 Correct 418 ms 55376 KB Output is correct
17 Correct 51 ms 28616 KB Output is correct
18 Correct 28 ms 28940 KB Output is correct
19 Correct 21 ms 28748 KB Output is correct
20 Correct 120 ms 28912 KB Output is correct
21 Correct 421 ms 49296 KB Output is correct
22 Correct 661 ms 82248 KB Output is correct