Submission #1236816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236816		nikd	Werewolf (IOI18_werewolf)	C++20	34 / 100	218 ms	74060 KiB

werewolf

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

struct sparse_min{
    int n, k;
    vector<vector<int>> st;
    vector<int> lg;
    sparse_min(vector<int> &v): n(v.size()){
        lg.resize(n+1);
        lg[1] = 0;
        for(int i = 2; i<=n; i++) lg[i] = lg[i/2]+1;
        k= lg[n]+1;
        st.resize(k+1, vector<int>(n));
        copy(v.begin(), v.end(), st[0].begin());
        for(int j = 1; j<=k; j++){
            for(int i= 0; i+(1<<j)-1<n; i++){
                st[j][i] = min(st[j-1][i], st[j-1][i+(1<<(j-1))]);
            }
        }
    }
    int q(int l, int r){
        if(l>r) swap(l, r);
        int p2 = lg[r-l+1];
        return min(st[p2][l], st[p2][r-(1<<p2)+1]);
    }
};

struct sparse_max{
    int n, k;
    vector<vector<int>> st;
    vector<int> lg;
    sparse_max(vector<int> &v): n(v.size()){
        lg.resize(n+1);
        lg[1] = 0;
        for(int i = 2; i<=n; i++) lg[i] = lg[i/2]+1;
        k= lg[n]+1;
        st.resize(k+1, vector<int>(n));
        copy(v.begin(), v.end(), st[0].begin());
        for(int j = 1; j<=k; j++){
            for(int i= 0; i+(1<<j)-1<n; i++){
                st[j][i] = max(st[j-1][i], st[j-1][i+(1<<(j-1))]);
            }
        }
    }
    int q(int l, int r){
        if(l>r) swap(l, r);
        int p2 = lg[r-l+1];
        return max(st[p2][l], st[p2][r-(1<<p2)+1]);
    }
};

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) {
    
    vector<vector<int>> adj(N);
    for(int i = 0; i<X.size(); i++){
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    vector<int> idx(N, 0);
    vector<int> val(N);
    int st;
    for(int i = 0; i<N; i++) if(adj[i].size() == 1) st = i;
    function<void(int, int, int)> dfs = [&](int v, int p, int i){
        idx[v] = i;
        val[i] = v;
        for(int u: adj[v]){
            if(u!=p) dfs(u, v, i+1);
        }
        return;
    };
    dfs(st, -1, 0);
    sparse_min st_mn(val);
    sparse_max st_mx(val);
    vector<int> sol(E.size(), 0);
    for(int i = 0; i<S.size(); i++){
        int ll = idx[S[i]];
        int rr = idx[E[i]];
        int l = ll;
        int r = rr;
        if(l>r) swap(l, r);
        r +=1;
        while(1){
            if(r-l<1){
                sol[i] = 0; break;
            }
            int m = (l+r)/2;
            
            int m1 = st_mn.q(ll, m);
            int m2 = st_mx.q(m, rr);
            if(m1>=L[i] && m2 <= R[i]){
                sol[i] = 1; break;
            }
            if(m1<L[i] && m2 > R[i]){
                sol[i] = 0; break;
            }
            if(ll<=rr){
                if(m1<L[i]){
                    r = m;
                }
                if(m2>R[i]){
                    l = m+1;
                }
            }
            else{
                if(m1 < L[i]){
                    l = m+1;
                }
                if(m2>R[i]){
                    r = m;
                }
            }
        }
    }
    return sol;
}

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