oj.uz

Submission #441690

# Submission time Handle Problem Language Result Execution time Memory
441690 2021-07-05T19:48:04 Z JovanB Colors (RMI18_colors) C++17
100 / 100
 766 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 rnk[MAXN+5];
    struct operacija{
        int a, b, rnka, rnkb;
    };
    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++) rnk[i] = 0;
    }
    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, rnk[a1], rnk[b1]});
        if(a1 == b1) return;
        if(rnk[a1] < rnk[b1]) swap(a1, b1);
        if(rnk[a1] == rnk[b1]) rnk[a1]++;
        par[b1] = a1;
    }
    void rollback(){
        int a = st.top().a;
        int b = st.top().b;
        rnk[a] = st.top().rnka;
        rnk[b] = st.top().rnkb;
        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) & 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;

    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);

    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: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 92 ms 28544 KB Output is correct
2 Correct 46 ms 29120 KB Output is correct
3 Correct 22 ms 28944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 28740 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 28524 KB Output is correct
2 Correct 50 ms 29056 KB Output is correct
3 Correct 22 ms 28748 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 28524 KB Output is correct
2 Correct 50 ms 29056 KB Output is correct
3 Correct 22 ms 28748 KB Output is correct
4 Correct 190 ms 31616 KB Output is correct
5 Correct 469 ms 50924 KB Output is correct
6 Correct 766 ms 72376 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 28544 KB Output is correct
2 Correct 46 ms 29120 KB Output is correct
3 Correct 22 ms 28944 KB Output is correct
4 Correct 102 ms 28524 KB Output is correct
5 Correct 50 ms 29056 KB Output is correct
6 Correct 22 ms 28748 KB Output is correct
7 Correct 98 ms 29980 KB Output is correct
8 Correct 47 ms 29072 KB Output is correct
9 Correct 22 ms 28864 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 28748 KB Output is correct
2 Correct 446 ms 51656 KB Output is correct
3 Correct 453 ms 62408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 28620 KB Output is correct
2 Correct 31 ms 29292 KB Output is correct
3 Correct 24 ms 28856 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 28544 KB Output is correct
2 Correct 46 ms 29120 KB Output is correct
3 Correct 22 ms 28944 KB Output is correct
4 Correct 94 ms 28740 KB Output is correct
5 Correct 102 ms 28524 KB Output is correct
6 Correct 50 ms 29056 KB Output is correct
7 Correct 22 ms 28748 KB Output is correct
8 Correct 190 ms 31616 KB Output is correct
9 Correct 469 ms 50924 KB Output is correct
10 Correct 766 ms 72376 KB Output is correct
11 Correct 98 ms 29980 KB Output is correct
12 Correct 47 ms 29072 KB Output is correct
13 Correct 22 ms 28864 KB Output is correct
14 Correct 181 ms 28748 KB Output is correct
15 Correct 446 ms 51656 KB Output is correct
16 Correct 453 ms 62408 KB Output is correct
17 Correct 53 ms 28620 KB Output is correct
18 Correct 31 ms 29292 KB Output is correct
19 Correct 24 ms 28856 KB Output is correct
20 Correct 126 ms 31172 KB Output is correct
21 Correct 478 ms 55368 KB Output is correct
22 Correct 720 ms 89524 KB Output is correct