Submission #819263

#	Time	Username	Problem	Language	Result	Execution time	Memory
819263		vjudge1	Werewolf (IOI18_werewolf)	C++17	15 / 100	231 ms	58640 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

template<typename T>
struct SparseTable {
    int len;
    vector<vector<T>> st;
    T (*F) (T, T);
    void init(vector<T> &a, T (*f) (T, T)) {
        F = f;
        len = (int)a.size();
        int mxpw = 32 - __builtin_clz(len);
        st.resize(mxpw);
        st[0] = a;
        for(int k = 1; k < mxpw; k++) {
            st[k].resize(len - (1 << k));
            for(int i = 0; i < (int)st[k].size(); i++) 
                st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
        }
    }
    T get(int l, int r) {
        if(r > l || l < 0 || r >= len) {
            cerr << "Wrong range in Sparse Table\n";
            cerr << "size = " << len << '\n';
            cerr << "range query: " << '[' << l << ", " << r <<  ']' << '\n';
            exit(1);
        }
        int mxpw = 31 - __builtin_clz(r - l + 1);
        return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
    }
};

int n, m, q;
const int N = 2e5 + 10;
vector<int> g[N];

vector<int> cnt;
vector<bool> us;
void dfs(int s, int l, int r) {
    us[s] = 1;
    cnt[s]++;
    for(int to : g[s]) {
        if(us[to] || to > r || to < l) continue;
        dfs(to, l, r);
    }
}

vector<int> order;
int tin[N];

void tour(int s, int p) {
    tin[s] = (int)order.size();
    order.push_back(s);
    for(int to : g[s]) 
        if(to != p) 
            tour(to, s);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
    n = N, m = (int)X.size(), q = (int)S.size();
    vector<int> res(q);
    
    for(int i = 0; i < m; i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    if(n <= 3000 && q <= 3000) {
        for(int i = 0; i < q; i++) {
            cnt.assign(n, 0);
            us.assign(n, false);
            dfs(S[i], L[i], n - 1);
            us.assign(n, false);
            dfs(E[i], 0, R[i]);
            if(*max_element(cnt.begin(), cnt.end()) > 1)
                res[i] = 1;
        }
        return res;
    }
    int root = 0;
    while(root < n && g[root].size() > 1) root++;
    tour(root, root);
    SparseTable<int> mn, mx;
    mn.init(order, [](int a, int b) {return (a > b ? b : a);});
    mx.init(order, [](int a, int b) {return (a < b ? b : a);});
    for(int i = 0; i < q; i++) {
        int x = tin[S[i]], y = tin[E[i]], lb, rb;
        int sl = x, sr = x, el = y, er = y;
        lb = x, rb = n;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mn.get(x, mid) >= L[i]) lb = mid;
            else rb = mid;
        }
        sr = lb;
        
        lb = 0, rb = x;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mn.get(mid, x) >= L[i]) rb = mid;
            else lb = mid;
        }
        sl = rb;
        
        lb = y, rb = n;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mx.get(y, mid) <= R[i]) lb = mid;
            else rb = mid;
        }
        er = lb;
        
        lb = 0, rb = y;
        while(rb - lb > 1) {
            int mid = (lb + rb) / 2;
            if(mx.get(mid, y) <= R[i]) rb = mid;
            else lb = mid;
        }
        el = rb;
        int ll = max(sl, el), rr = min(sr, er);
        res[i] = (ll <= rr);
    }
    return res;
}

Compilation message (stderr)

werewolf.cpp: In instantiation of 'void SparseTable<T>::init(std::vector<_Tp>&, T (*)(T, T)) [with T = int]':
werewolf.cpp:88:62:   required from here
werewolf.cpp:20:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   20 |                 st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
      |                                                                ~~^~~

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