제출 #819289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
819289		vjudge1	늑대인간 (IOI18_werewolf)	C++17	49 / 100	1319 ms	67116 KiB

werewolf

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

using namespace std;

template<typename T> 
struct SparseTable {
    vector<vector<T>> st;
    T (*F) (T, T);
    int len;
    void init(vector<T> &a, T(*f)(T, T)) {
        len = (int)a.size();
        int mxpow = 32 - __builtin_clz(len);
        F = f;
        st.resize(mxpow);
        st[0] = a;
        for(int k = 1; k < mxpow; k++) {
            st[k].resize(len - (1 << k) + 1);
            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(l > r || l < 0 || r >= len) {
            exit(1);
        }
        int k = 31 - __builtin_clz(r - l + 1);
        return F(st[k][l], st[k][r - (1 << k) + 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 && m <= 6000) {
        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, sr, el, er;
        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 = -1, 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 = -1, 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;
}

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