oj.uz

Submission #332483

# Submission time Handle Problem Language Result Execution time Memory
332483 2020-12-02T17:27:58 Z Vladth11 Colors (RMI18_colors) C++14
100 / 100
 1115 ms 106156 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;

const ll NMAX = 150001;
const ll INF = (1 << 30);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 14;
const ll delta = 0.0000001;

int n, m;
vector <int> v[NMAX];
int ok;
int a[NMAX], b[NMAX];

class DSU {
    int minim[NMAX], cnt[NMAX];
    struct dsu_save {
        int w, x, y, size_x, size_y, parent_x, parent_y, mini_x, mini_y;
    };
    int parent[NMAX];
    int root(int x) {
        if(x == parent[x])
            return x;
        return root(parent[x]);
    }
public:
    stack <dsu_save> stiva;
    void init() {
        while(stiva.size())
            stiva.pop();
        for(int i = 1; i <= n; i++) {
            cnt[i] = 1;
            parent[i] = i;
            minim[i] = a[i];
        }
    }
    void merge(int node, int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y)
            return;
        dsu_save ss = {node, x, y,cnt[x], cnt[y], parent[x], parent[y], minim[x], minim[y]};
        stiva.push(ss);
        if(cnt[x] > cnt[y]) {
            cnt[x] += cnt[y];
            cnt[y] = 0;
            parent[y] = x;
            minim[x] = min(minim[x], minim[y]);
        } else {
            cnt[y] += cnt[x];
            cnt[x] = 0;
            parent[x] = y;
            minim[y] = min(minim[x], minim[y]);
        }
    }
    void rollback() {
        if(stiva.size() == 0)
            return;
        dsu_save e = stiva.top();
        int x = e.x;
        int y = e.y;
        cnt[x] = e.size_x;
        cnt[y] = e.size_y;
        parent[x] = e.parent_x;
        parent[y] = e.parent_y;
        minim[x] = e.mini_x;
        minim[y] = e.mini_y;
        stiva.pop();
    }
    int minimm(int x) {
        x = root(x);
        return minim[x];
    }
};

class AINT {
    vector <pii> aint[4 * NMAX];
    DSU dsu;
public:
    void init() {
        dsu.init();
    }
    void update(int node, int st, int dr, int a, int b, pii x) {
        if(a > b)
            return;
        if(a <= st && dr <= b) {
            aint[node].push_back(x);
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid) {
            update(node * 2, st, mid, a, b, x);
        }
        if(b > mid) {
            update(node * 2 + 1, mid + 1, dr, a, b, x);
        }
    }
    void DFS(int node, int st, int dr) {
        for(auto x : aint[node]) {
            dsu.merge(node, x.first, x.second);
        }
       // debug(node);
        if(st == dr) {
            for(auto x : v[st]) {
               // debug(st);
                if(st != dsu.minimm(x)) {
                    //debug(dsu.minimm(x));
                    ok = 0;
                }
            }
        }
        int mid = (st + dr) / 2;
        if(st != dr) {
            DFS(node * 2, st, mid);
            DFS(node * 2 + 1, mid + 1, dr);
        }
        while(dsu.stiva.size() > 0 && dsu.stiva.top().w == node) {
            dsu.rollback();
        }
        aint[node].clear();
    }
} DC;

int main() {
    
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        int i;
        for(i = 1; i <= n; i++) {
            v[i].clear();
            cin >> a[i];
        }
        for(i = 1; i <= n; i++) {
            cin >> b[i];
            v[b[i]].push_back(i);
        }
        DC.init();
        ok = 1;
        for(i = 1; i <= n; i++) {
            if(a[i] < b[i])
                ok = 0;
        }
            for(i = 1; i <= m; i++) {
                int x;
                int y;
                cin >> x >> y;
                if(ok)
                    DC.update(1, 1, n, max(b[x], b[y]), min(a[x], a[y]), {x, y});
            }
            if(ok)
            DC.DFS(1, 1, n);
       // debug(ok);
        cout << ok << "\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 19308 KB Output is correct
2 Correct 63 ms 18796 KB Output is correct
3 Correct 20 ms 18540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 19952 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 19308 KB Output is correct
2 Correct 64 ms 18540 KB Output is correct
3 Correct 18 ms 18284 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 19308 KB Output is correct
2 Correct 64 ms 18540 KB Output is correct
3 Correct 18 ms 18284 KB Output is correct
4 Correct 322 ms 21100 KB Output is correct
5 Correct 722 ms 48312 KB Output is correct
6 Correct 1078 ms 80448 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 19308 KB Output is correct
2 Correct 63 ms 18796 KB Output is correct
3 Correct 20 ms 18540 KB Output is correct
4 Correct 162 ms 19308 KB Output is correct
5 Correct 64 ms 18540 KB Output is correct
6 Correct 18 ms 18284 KB Output is correct
7 Correct 159 ms 19564 KB Output is correct
8 Correct 70 ms 18796 KB Output is correct
9 Correct 19 ms 18412 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 20588 KB Output is correct
2 Correct 707 ms 50292 KB Output is correct
3 Correct 738 ms 57160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 18796 KB Output is correct
2 Correct 35 ms 19052 KB Output is correct
3 Correct 22 ms 18412 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 19308 KB Output is correct
2 Correct 63 ms 18796 KB Output is correct
3 Correct 20 ms 18540 KB Output is correct
4 Correct 156 ms 19952 KB Output is correct
5 Correct 162 ms 19308 KB Output is correct
6 Correct 64 ms 18540 KB Output is correct
7 Correct 18 ms 18284 KB Output is correct
8 Correct 322 ms 21100 KB Output is correct
9 Correct 722 ms 48312 KB Output is correct
10 Correct 1078 ms 80448 KB Output is correct
11 Correct 159 ms 19564 KB Output is correct
12 Correct 70 ms 18796 KB Output is correct
13 Correct 19 ms 18412 KB Output is correct
14 Correct 306 ms 20588 KB Output is correct
15 Correct 707 ms 50292 KB Output is correct
16 Correct 738 ms 57160 KB Output is correct
17 Correct 77 ms 18796 KB Output is correct
18 Correct 35 ms 19052 KB Output is correct
19 Correct 22 ms 18412 KB Output is correct
20 Correct 208 ms 21228 KB Output is correct
21 Correct 700 ms 53812 KB Output is correct
22 Correct 1115 ms 106156 KB Output is correct