Submission #1306149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306149		fafnir	Werewolf (IOI18_werewolf)	C++20	49 / 100	4090 ms	52176 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)

template<typename T>
struct RMin {
    T operator()(const T& a, const T& b) {
        if (a < b) return a;
        return b;
    }
};

template<typename T>
struct RMax {
    T operator()(const T& a, const T& b) {
        if (a > b) return a;
        return b;
    }
};


// Op: Aggregation (min/max/sum/gcd)
// T:  Underlying type
// For non idempotent aggregation (e.g. sum), need query_log,
// else query_const
template<typename T, typename Op>
class SparseTable {
private:
    Op m_op;
    vector<vector<T>> m_table;
    size_t m_n;
    size_t m_log;
    void build(const vector<T>& data) {
        copy(data.begin(), data.end(), m_table[0].begin());
        for (int i = 1; i <= m_log; ++i) {
            for (int j = 0; j + (1 << i) <= m_n; ++j) {
                m_table[i][j] = m_op(m_table[i-1][j], m_table[i-1][j + (1 << (i-1))]);
            }
        }
    }
    int log2_floor(unsigned long i) {
        return i ? 63 - __builtin_clzll(i) : -1;
    }
public:
    SparseTable(vector<T>& data, Op op) : m_n{data.size()}, m_log{0}, m_op{op} {
        while ((1 << (m_log+1)) <= m_n) {
            ++m_log;
        }
        m_table.resize(m_log + 1, vector<T>(m_n));
        build(data);
    }
    T query_const(int l, int r) {
        int i = log2_floor(r - l + 1);
        return m_op(m_table[i][l],
                m_table[i][r - (1 << i) + 1]);
    }

    T query_log(int l, int r) {
        T res{};
        for (int i = m_log; i >= 0; --i) {
            if ((1 << i) <= r - l + 1) {
                res = m_op(res, m_table[i][l]);
                l += 1 << i;
            }
        }
        return res;
    }
};


// Two ranges [l0, r0]
//            [l1, r1]
// Intersect if there is x s.t. l0 <= x <= r0 and l1 <= x <= r1
// Assuming l1 <= r1 and l0 <= r0
// l0 <= r1 && l1 <= r0
bool range_intersect(const pair<int,int>& a, const pair<int,int>& b) {
    return a.first <= b.second && b.first <= a.second;
}



vector<bool> reachable(vector<vector<int>>& adjList, int start, int lo, int hi) {
    const int N = adjList.size();
    vector<bool> vis(N, false);

    queue<int> q;
    if (start >= lo && start <= hi) {
        q.push(start);
        vis[start] = true;
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto& v : adjList[u]) {
            if (lo <= v && v <= hi && !vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }

    return vis;
}

// Invariant: Interval [up,x] valid
int find_left(SparseTable<int, RMin<int>>& st_min,
    SparseTable<int, RMax<int>>& st_max, int x, int l, int r) {
    int lb = 0;
    int up = x;
    while (lb != up) {
        int s = (lb + up) / 2;

        int mn = st_min.query_const(s, x);
        int mx = st_max.query_const(s, x);

        if (mn >= l && mx <= r) {
            up = s;
        } else {
            lb = s+1;
        }
    }
    return up;
}

// Invariant: Interval [x,lb] valid
int find_right(SparseTable<int, RMin<int>>& st_min,
    SparseTable<int, RMax<int>>& st_max, int x, int l, int r, int N) {
    int lb = x;
    int up = N-1;
    while (lb != up) {
        int s = (lb + up + 1) / 2;

        int mn = st_min.query_const(x, s);
        int mx = st_max.query_const(x, s);

        if (mn >= l && mx <= r) {
            lb = s;
        } else {
            up = s-1;
        }
    }
    return lb;
}



vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                            vector<int> S, vector<int> E,
                            vector<int> L, vector<int> R) {
    int Q = S.size();
    int M = X.size();
    
    vector<int> A(Q);
    vector<vector<int> > adj(N);
    REP(i, M) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    // Check for line graph
    bool isLine = true;

    REP(i, N) {
        isLine = isLine && (adj[i].size() <= 2);
    }

    // Subtask 3: Line graph
    if (isLine) {
        
        // Linearize graph
        int u = -1;
        int parent = -1;
        REP(i, N) {
            if (adj[i].size() == 1) {u = i; break;}
        }

        vector<int> order(N);
        vector<int> pos(N);
        REP(i, N) {
            order[i] = u;
            pos[u] = i;
            // If the first node in adjacency list is parent
            // then need to choose the other one (index 1)
            int next = (adj[u][0] == parent);
            parent = u;
            u = adj[u][next];
        }

        SparseTable<int,RMin<int>> st_min(order, RMin<int>());
        SparseTable<int,RMax<int>> st_max(order, RMax<int>());

        REP(i, Q) {

            pair<int,int> s_int;
            if (S[i] >= L[i] && E[i] <= R[i]) {
                pair<int,int> s_int(find_left(st_min, st_max, pos[S[i]], L[i], N-1),
                                    find_right(st_min, st_max, pos[S[i]], L[i], N-1, N));

                pair<int,int> e_int(find_left(st_min, st_max, pos[E[i]], 0, R[i]),
                                    find_right(st_min, st_max, pos[E[i]], 0, R[i], N));
            
                A[i] = range_intersect(s_int, e_int);
            }
        }
        
    } else {

        REP(i, Q) {
            vector<bool> reach_S = reachable(adj, S[i], L[i], N-1);
            vector<bool> reach_E = reachable(adj, E[i], 0, R[i]);
                
            REP(v, N) {
                A[i] |= reach_S[v] && reach_E[v];
                if (A[i]) {break;}
            }
        }

    }

    return A;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51