Submission #1296530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296530		cnam9	Colors (RMI18_colors)	C++20	0 / 100	805 ms	589824 KiB

colors

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <math.h>

using namespace std;

constexpr int N = 1.5e5 + 5;

int n, m;
int a[N], b[N];
vector<int> graph[N];
int cnta[N];
int cntb[N];
bool has_source[N];

bool necessaryCheck() {
    for (int u = 1; u <= n; u++) {
        if (a[u] < b[u])
            return false;
    }
    fill(cnta + 1, cnta + n + 1, 0);
    fill(cntb + 1, cntb + n + 1, 0);

    for (int u = 1; u <= n; u++) {
        cnta[a[u]]++;
    }
    for (int u = 1; u <= n; u++) {
        cntb[b[u]]++;
    }
    for (int c = 1; c <= n; c++) {
        if (cntb[c] && !cnta[c])
            return false;
    }
    return true;
}

namespace subtaskStar {
    int pivot;

    bool check() {
        if (m != n - 1) return false;
        for (pivot = 1; pivot <= n; pivot++) {
            if (graph[pivot].size() == n - 1) return true;
        }
        return false;
    }

    bool solve() {
        memset(has_source + 1, 0, n);
        for (int u = 1; u <= n; u++) {
            if (a[u] <= a[pivot]) {
                has_source[a[u]] = true;
            }
            if (a[u] > b[u] && b[u] < b[pivot]) return false;
        }
        for (int u = 1; u <= n; u++) {
            if (a[u] > b[u] && !has_source[b[u]]) return false;
        }
        return true;
    }
}

vector<int> withb[N];

namespace subtaskTreePermutation {
    bool check() {
        if (m != n - 1) return false;
        for (int c = 1; c <= n; c++) {
            if (cnta[c] != 1) return false;
        }
        return true;
    }

    int witha[N];

    constexpr int logN = static_cast<int>(log2(N));
    struct {
        int parent;
        pair<int, int> interval;
    } up[N][logN + 1];

    int timer;
    int tin[N], tout[N];

    inline pair<int, int> operator&(const pair<int, int> &i, const pair<int, int> &j) {
        return {max(i.first, j.first), min(i.second, j.second)};
    }
    inline void operator&=(pair<int, int> &i, const pair<int, int> &j) {
        i.first = max(i.first, j.first);
        i.second = min(i.second, j.second);
    }

    void dfs(int u, int p) {
        tin[u] = ++timer;

        up[u][0] = {p, pair<int, int>{b[u], a[u]}};
        for (int i = 0; i < logN; i++) {
            up[u][i + 1].parent = up[up[u][i].parent][i].parent;
            up[u][i + 1].interval = up[u][i].interval & up[up[u][i].parent][i].interval;
        }

        for (int v : graph[u]) {
            if (v == p) continue;
            dfs(v, u);
        }

        tout[u] = timer;
    }

    inline bool is_ancestor(int a, int d) {
        return tin[a] <= tin[d] && tout[d] <= tout[a];
    }

    pair<int, int> query(int u, int v) {
        if (u == v) return {b[u], a[u]};
        pair<int, int> res = {1, n};
        if (is_ancestor(u, v)) { }
        else if (is_ancestor(v, u)) swap(u, v);
        else {
            // jumps u until ancestor of v
            for (int i = logN; i >= 0; i--) {
                if (is_ancestor(up[u][i].parent, v)) continue;
                res &= up[u][i].interval;
                u = up[u][i].parent;
            }
            res &= up[u][1].interval;
            u = up[u][1].parent;
        }
        // jumps v until child of u
        for (int i = logN; i >= 0; i--) {
            if (is_ancestor(up[v][i].parent, u)) continue;
            res &= up[v][i].interval;
            v = up[v][i].parent;
        }
        res &= up[v][0].interval;
        return res;
    }

    void clear() {
        for (int c = 1; c <= n; c++) {
            withb[c].clear();
        }
    }

    bool solve() {
        for (int u = 1; u <= n; u++) {
            witha[a[u]] = u;
            withb[b[u]].push_back(u);
        }

        timer = 0;
        dfs(1, 1);

        for (int c = 1; c <= n; c++) {
            int p = witha[c];
            for (int u : withb[c]) {
                pair<int, int> spectrum = query(u, p);
                if (c < spectrum.first || c > spectrum.second) {
                    return false;
                }
            }
        }
        return true;
    }
}

// namespace subtaskComplete {
//     bool check() {
//         return (long long) m * (m - 1) / 2 == n;
//     }

//     bool solve() {
//         return true;
//     }
// }

// namespace subtaskLine {
//     int flattened[N];

//     int last[N];
//     int next[N];

//     bool solve() {
//         int head;
//         while (graph[head].size() >= 2) continue;

//         int i = 1;
//         flattened[0] = -1;
//         flattened[1] = head;

//         while (i < n) {
//             for (int u : graph[head]) {
//                 if (u == flattened[i - 1]) continue;
//                 flattened[++i] = head = u;
//                 break;
//             }
//         }

//         deque<int> dql, dqr;

//         for (int i = n; i; i--) {
//             int u = flattened[i];

//         }

//         return true;
//     }
// }

namespace subtask7 {
    bool check() {
        return true;
    }

    vector<int> witha[N];

    inline pair<int, int> operator&(const pair<int, int> &i, const pair<int, int> &j) {
        return {max(i.first, j.first), min(i.second, j.second)};
    }
    inline void operator&=(pair<int, int> &i, const pair<int, int> &j) {
        i.first = max(i.first, j.first);
        i.second = min(i.second, j.second);
    }

    void clear() {
        for (int c = 1; c <= n; c++) {
            witha[c].clear();
            withb[c].clear();
        }
    }

    bool visited[N];

    bool solve() {
        for (int u = 1; u <= n; u++) {
            witha[a[u]].push_back(u);
            withb[b[u]].push_back(u);
        }

        for (int c = 1; c <= n; c++) {
            memset(visited + 1, 0, n);

            queue<int> q;
            for (int s : witha[c]) {
                q.push(s);
                visited[s] = true;
            }

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (int v : graph[u]) {
                    if (visited[v] || a[v] < c || b[v] > c) continue;
                    visited[v] = true;
                    q.push(v);
                }
            }

            for (int t : withb[c]) {
                if (!visited[t]) {
                    return false;
                }
            }
        }
        return true;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt", "r", stdin);
    // freopen("syncolor.inp", "r", stdin);
    // freopen("syncolor.out", "w", stdout);

int T;
cin >> T;

while (T--)
{
    cin >> n >> m;

    for (int u = 1; u <= n; u++) { cin >> a[u]; }
    for (int u = 1; u <= n; u++) { cin >> b[u]; }

    for (int e = 0; e < m; e++) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    if (!necessaryCheck()) {
        cout << "0\n";
        continue;
    }

    if (subtaskStar::check()) {
        cout << subtaskStar::solve() << '\n';
        goto next;
    }
    // if (subtaskComplete::check()) {
    //     cout << subtaskComplete::solve() << '\n';
    //     goto next;
    // }
    if (subtaskTreePermutation::check()) {
        cout << subtaskTreePermutation::solve() << '\n';
        subtaskTreePermutation::clear();
        goto next;
    }
    cout << subtask7::solve() << '\n';
    subtask7::clear();

next:
    for (int i = 1; i <= n; i++) {
        graph[i].clear();
    }
}

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22