oj.uz

Submission #709858

# Submission time Handle Problem Language Result Execution time Memory
709858 2023-03-14T17:22:27 Z Cyanmond Werewolf (IOI18_werewolf) C++17
0 / 100
 733 ms 28824 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

struct UnionFind {
    int n;
    std::vector<int> data;
    UnionFind(int n_) : n(n_) {
        data.assign(n, -1);
    }

    int find(int v) {
        if (data[v] < 0) return v;
        else return data[v] = find(data[v]);
    }

    void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (data[a] > data[b]) std::swap(a, b);
        data[a] += data[b];
        data[b] = a;
    }
};

constexpr int inf = 1 << 30;

template <class M>
class SegmentTree {
    using T = typename M::T;
    int n, size;
    std::vector<T> data;

    void update(int i) {
        data[i] = M::op(data[2 * i], data[2 * i + 1]);
    }

    public:
    SegmentTree() {}
    SegmentTree(const std::vector<T> &vec) {
        n = (int)vec.size();
        size = 1;
        while (size < n) {
            size *= 2;
        }
        data.assign(2 * size, M::e());
        std::copy(vec.begin(), vec.end(), data.begin() + size);
        for (int i = size - 1; i >= 1; --i) update(i);
    }

    void set(int i, const T &v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    T fold(int l, int r) {
        T pl = M::e(), pr = M::e();
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l & 1) pl = M::op(pl, data[l++]);
            if (r & 1) pr = M::op(data[--r], pr);
        }
        return M::op(pl, pr);
    }

    int max_right(int l, int v) {
        int ok = n, ng = l;
        while (ok - ng > 1) {
            const auto mid = (ok + ng) / 2;
            if (fold(l, mid).second <= v) ng = mid;
            else ok = mid;
        }
        return ng;
    }

    int min_left(int r, int v) {
        int ok = -1, ng = r;
        while (ng - ok > 1) {
            const auto mid = (ok + ng) / 2;
            if (fold(mid, r).second <= v) ng = mid;
            else ok = mid;
        }
        return ng;
    }
};

struct MonoidMinMax {
    using T = std::pair<int, int>;
    static T op(const T &a, const T &b) {
        return {std::min(a.first, b.first), std::max(a.second, b.second)};
    }
    static T e() {
        return {inf, -1};
    }
};

constexpr int B = 3;

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S,
                                std::vector<int> E, std::vector<int> L, std::vector<int> R) {
    const int M = (int)X.size();
    const int Q = (int)S.size();
    std::vector<int> answer(Q);

    std::vector<std::vector<int>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    int v = -1;
    for (int i = 0; i < N; ++i) {
        if (graph[i].size() == 1) {
            v = i;
        }
    }
    std::vector<int> id(N), rid(N);
    {
        int p = -1;
        int cnt = 0;
        while (true) {
            id[v] = cnt;
            rid[cnt] = v;
            ++cnt;
            int w = v;
            for (const int t : graph[v]) if (t != p) {
                p = v;
                v = t;
                break;
            }
            if (w == v) {
                break;
            }
        }
    }
    std::vector<std::pair<int, int>> vec(N);
    for (int i = 0; i < N; ++i) {
        vec[i] = {rid[i], rid[i]};
    }
    SegmentTree<MonoidMinMax> seg(vec);
    for (int i = 0; i < Q; ++i) {
        const int a = id[S[i]], b = id[E[i]];
        if (a < b) {
            const int x = seg.min_left(b + 1, R[i]);
            if (x <= a) {
                answer[i] = true;
            } else {
                if (vec[x].first < L[i]) answer[i] = false;
                else if (seg.fold(a, x).first >= L[i]) answer[i] = true;
                else answer[i] = false;
            }
        } else {
            const int x = seg.max_right(b, R[i]);
            if (x > a) {
                answer[i] = true;
            } else {
                if (vec[x - 1].first < L[i]) answer[i] = false;
                else if (seg.fold(x, a + 1).first >= L[i]) answer[i] = true;
                else answer[i] = false;
            }
        }
    }
    return answer;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 28704 KB Output is correct
2 Correct 668 ms 28824 KB Output is correct
3 Correct 733 ms 28700 KB Output is correct
4 Correct 702 ms 28804 KB Output is correct
5 Correct 722 ms 28680 KB Output is correct
6 Correct 663 ms 28704 KB Output is correct
7 Correct 627 ms 28716 KB Output is correct
8 Correct 695 ms 28704 KB Output is correct
9 Incorrect 463 ms 28808 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -