Submission #332483

#	Time	Username	Problem	Language	Result	Execution time	Memory
332483		Vladth11	Colors (RMI18_colors)	C++14	100 / 100	1115 ms	106156 KiB

colors

#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 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22