Submission #1306888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306888		fafnir	늑대인간 (IOI18_werewolf)	C++20	49 / 100	4094 ms	30200 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;
}


int fufind(vector<int>& fu, int x) {
    if (fu[x] < 0) {return x;}      // x is root
    fu[x] = fufind(fu, fu[x]);
    return fu[x];
}

void fujoin(vector<int>& fu, vector<int>& pos_sml, vector<int>& pos_big, int x, int y) {
    x = fufind(fu, x);
    y = fufind(fu, y);

    if (x != y) {
        fu[y] = x;
        pos_sml[x] = min(pos_sml[x], pos_sml[y]);
        pos_big[x] = max(pos_big[x], pos_big[y]);
    }
}


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
    // DSU solution
    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;
            int next = (adj[u][0] == parent);
            parent = u;
            u = adj[u][next];
        }


        // Idea: Define V_L as set of vertices reachable from S
        //       that have values in range [L,N-1]
        //       They form an interval surrounding S
        
        vector<int> fu(N);
        vector<int> pos_sml(N);
        vector<int> pos_big(N);
        vector<pair<int,int>> Lrange(Q);
        vector<pair<int,int>> Rrange(Q);

        // Sort queries by L[i] (non-increasing)
        vector<int> idx(Q);
        REP(i, Q) {idx[i] = i;}
        sort(idx.begin(), idx.end(), [&](int i0, int i1) {
            return L[i0] > L[i1];
        });

        // Initialize DSU structure
        REP(i, N) {
            fu[i] = -1;
            pos_sml[i] = pos_big[i] = pos[i];
        }


        // Calculate V_L 
        int next = N-1;
        REP(i, Q) {
            int limit = L[idx[i]];
            for (; next >= limit; --next) {
                for (int u : adj[next]) {
                    if (u >= limit) {
                        fujoin(fu, pos_sml, pos_big, next, u);
                    }
                }
            }

            int lead = fufind(fu, S[idx[i]]);
            Lrange[idx[i]] = make_pair(pos_sml[lead], pos_big[lead]);
        }


        // Calculate V_R
        REP(i, Q) {idx[i] = i;}
        vector<int> idx1(Q);
        REP(i, Q) {idx1[i] = i;}
        sort(idx1.begin(), idx1.end(), [&](int i0, int i1) {
            return R[i0] < R[i1];
        });
        REP(i, N) {
            fu[i] = -1;
            pos_sml[i] = pos_big[i] = pos[i];
        }
        next = 0;
        REP(i, Q) {
            int limit = R[idx1[i]];
            for(; next <= limit; ++next) {
                for (int u : adj[next]) {
                    if (u <= limit) {
                        fujoin(fu, pos_sml, pos_big, next, u);
                    }
                }
            } 

            int lead = fufind(fu, E[idx1[i]]);
            Rrange[idx1[i]] = make_pair(pos_sml[lead], pos_big[lead]);
        }


        REP(i,Q) {
            A[i] = range_intersect(Lrange[i], Rrange[i]);
        }


    } 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