oj.uz

Submission #445857

# Submission time Handle Problem Language Result Execution time Memory
445857 2021-07-19T23:25:53 Z JovanB Colors (RMI18_colors) C++17
100 / 100
 708 ms 89524 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 200000;

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

struct DSU{
    int n;
    int par[MAXN+5];
    int sz[MAXN+5];
    struct operacija{
        int a, b, sza, szb;
    };
    stack <operacija> st;
    void init(int g){
        n = g;
        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){
        int a1 = root(a);
        int b1 = root(b);
        st.push({a1, b1, sz[a1], sz[b1]});
        if(a1 == b1) return;
        if(sz[a1] < sz[b1]) swap(a1, b1);
        sz[a1] += sz[b1];
        par[b1] = a1;
    }
    void rollback(){
        int a = st.top().a;
        int b = st.top().b;
        sz[a] = st.top().sza;
        sz[b] = st.top().szb;
        par[a] = a;
        par[b] = b;
        st.pop();
    }
};

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

vector <pair <int, int>> edges;
vector <pair <int, int>> zivi[4*MAXN+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:81:18: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   81 |         for(auto c : zivi[node]) dsu.rollback();
      |                  ^
colors.cpp:87:14: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   87 |     for(auto c : zivi[node]) dsu.rollback();
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 30020 KB Output is correct
2 Correct 42 ms 29124 KB Output is correct
3 Correct 19 ms 28868 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 30432 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 29924 KB Output is correct
2 Correct 43 ms 29048 KB Output is correct
3 Correct 19 ms 28748 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 29924 KB Output is correct
2 Correct 43 ms 29048 KB Output is correct
3 Correct 19 ms 28748 KB Output is correct
4 Correct 175 ms 31608 KB Output is correct
5 Correct 431 ms 50872 KB Output is correct
6 Correct 708 ms 72296 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 30020 KB Output is correct
2 Correct 42 ms 29124 KB Output is correct
3 Correct 19 ms 28868 KB Output is correct
4 Correct 92 ms 29924 KB Output is correct
5 Correct 43 ms 29048 KB Output is correct
6 Correct 19 ms 28748 KB Output is correct
7 Correct 92 ms 29924 KB Output is correct
8 Correct 43 ms 29092 KB Output is correct
9 Correct 23 ms 28852 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 31608 KB Output is correct
2 Correct 394 ms 51580 KB Output is correct
3 Correct 426 ms 62336 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 29400 KB Output is correct
2 Correct 29 ms 29292 KB Output is correct
3 Correct 21 ms 28848 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 30020 KB Output is correct
2 Correct 42 ms 29124 KB Output is correct
3 Correct 19 ms 28868 KB Output is correct
4 Correct 101 ms 30432 KB Output is correct
5 Correct 92 ms 29924 KB Output is correct
6 Correct 43 ms 29048 KB Output is correct
7 Correct 19 ms 28748 KB Output is correct
8 Correct 175 ms 31608 KB Output is correct
9 Correct 431 ms 50872 KB Output is correct
10 Correct 708 ms 72296 KB Output is correct
11 Correct 92 ms 29924 KB Output is correct
12 Correct 43 ms 29092 KB Output is correct
13 Correct 23 ms 28852 KB Output is correct
14 Correct 194 ms 31608 KB Output is correct
15 Correct 394 ms 51580 KB Output is correct
16 Correct 426 ms 62336 KB Output is correct
17 Correct 55 ms 29400 KB Output is correct
18 Correct 29 ms 29292 KB Output is correct
19 Correct 21 ms 28848 KB Output is correct
20 Correct 122 ms 31224 KB Output is correct
21 Correct 419 ms 55128 KB Output is correct
22 Correct 631 ms 89524 KB Output is correct