oj.uz

답안 #441691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441691 2021-07-05T19:58:16 Z JovanB Colors (RMI18_colors) C++17
100 / 100
 763 ms 82280 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));
    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;

    //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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 28536 KB Output is correct
2 Correct 42 ms 28596 KB Output is correct
3 Correct 20 ms 28832 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 28664 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 28652 KB Output is correct
2 Correct 43 ms 28492 KB Output is correct
3 Correct 20 ms 28620 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 28652 KB Output is correct
2 Correct 43 ms 28492 KB Output is correct
3 Correct 20 ms 28620 KB Output is correct
4 Correct 175 ms 28492 KB Output is correct
5 Correct 452 ms 44640 KB Output is correct
6 Correct 763 ms 65544 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 28536 KB Output is correct
2 Correct 42 ms 28596 KB Output is correct
3 Correct 20 ms 28832 KB Output is correct
4 Correct 97 ms 28652 KB Output is correct
5 Correct 43 ms 28492 KB Output is correct
6 Correct 20 ms 28620 KB Output is correct
7 Correct 92 ms 28544 KB Output is correct
8 Correct 44 ms 28556 KB Output is correct
9 Correct 21 ms 28796 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 28528 KB Output is correct
2 Correct 403 ms 45696 KB Output is correct
3 Correct 498 ms 55388 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 28568 KB Output is correct
2 Correct 29 ms 29048 KB Output is correct
3 Correct 23 ms 28744 KB Output is correct

Subtask #8
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 28536 KB Output is correct
2 Correct 42 ms 28596 KB Output is correct
3 Correct 20 ms 28832 KB Output is correct
4 Correct 91 ms 28664 KB Output is correct
5 Correct 97 ms 28652 KB Output is correct
6 Correct 43 ms 28492 KB Output is correct
7 Correct 20 ms 28620 KB Output is correct
8 Correct 175 ms 28492 KB Output is correct
9 Correct 452 ms 44640 KB Output is correct
10 Correct 763 ms 65544 KB Output is correct
11 Correct 92 ms 28544 KB Output is correct
12 Correct 44 ms 28556 KB Output is correct
13 Correct 21 ms 28796 KB Output is correct
14 Correct 171 ms 28528 KB Output is correct
15 Correct 403 ms 45696 KB Output is correct
16 Correct 498 ms 55388 KB Output is correct
17 Correct 51 ms 28568 KB Output is correct
18 Correct 29 ms 29048 KB Output is correct
19 Correct 23 ms 28744 KB Output is correct
20 Correct 122 ms 28924 KB Output is correct
21 Correct 421 ms 49376 KB Output is correct
22 Correct 648 ms 82280 KB Output is correct