제출 #524606

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

werewolf

#include "werewolf.h"
#include <vector>
#include <set>
#include <iostream>

using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//#define int long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

const int SZ = 3e3 + 7;
const int R = 2e5 + 7;
const int LOG = 19;

vector<int> g[R];
int ver[R],pos[R];
int timer = 0;
vector<vector<int>> sp(R,vector<int> (LOG,2e9));
vector<vector<int>> sg(R,vector<int> (LOG,-2e9));
int mn[SZ][SZ];
int mx[SZ][SZ];

void dfs(int v,int p) {
    ver[timer] = v;
    pos[v] = timer;
    timer += 1;
    for(int u : g[v]) {
        if(u == p) continue;
        dfs(u,v);
    }
}

int get_min(int l,int r) {
    int k = __lg(r - l + 1);
    return min(sp[l][k],sp[r - (1 << k) + 1][k]);
}

int get_max(int l,int r) {
    int k = __lg(r - l + 1);
    return max(sg[l][k],sg[r - (1 << k) + 1][k]);
}

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 M = X.size(),Q = L.size();
    for(int i = 0; i < M; ++i) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    bool ok = (N - 1 == M);
    int cnt = 0;
    for(int i = 0; i < N; ++i) {
        if(g[i].size() == 1) {
            cnt += 1;
        }
    }
    ok &= (cnt == 2);
    if(!ok) {
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                mn[i][j] = 2e9;
                mx[i][j] = -2e9;
            }
        }
        set<pair<int,int>> st;
        for(int i = 0; i < N; ++i) {
            st.insert({0,i});
            mn[i][i] = i;
            while(st.size()) {
                pair<int,int> p = *st.begin();
                int v = p.ss;
                st.erase(st.begin());
                for(int u : g[v]) {
                    if(mn[i][u] > max(mn[i][v],u)) {
                        st.erase({mn[i][u],u});
                        mn[i][u] = max(mn[i][v],u);
                        st.insert({mn[i][u],u});
                    }
                }
            }
            st.insert({i,i});
            mx[i][i] = i;
            while(st.size()) {
                pair<int,int> p = *(--st.end());
                int v = p.ss;
                st.erase(--st.end());
                for(int u : g[v]) {
                    if(mx[i][u] < min(mx[i][v],u)) {
                        st.erase({mn[i][u],u});
                        mx[i][u] = min(mx[i][v],u);
                        st.insert({mx[i][u],u});
                    }
                }
            }
        }
        vector<int> ans(Q);
        for(int i = 0; i < Q; ++i) {
            int s = S[i],e = E[i];
            for(int v = 0; v < N; ++v) {
                if(mx[s][v] >= L[i] && mn[v][e] <= R[i]) {
                    ans[i] = 1;
                    break;
                }
            }
        }
        return ans;
    }
    int kor = 0;
    for(int i = 0; i < N; ++i) {
        if(g[i].size() == 1) {
            kor = i;
            break;
        }
    }
    dfs(kor,-1);
    for(int i = 0; i < timer; ++i) {
        sp[i][0] = ver[i];
        sg[i][0] = ver[i];
    }
    for(int log = 1; log < LOG; ++log) {
        for(int i = 0; i + (1 << (log - 1)) < timer; ++i) {
            sp[i][log] = min(sp[i][log - 1],sp[i + (1 << (log - 1))][log - 1]);
            sg[i][log] = max(sg[i][log - 1],sg[i + (1 << (log - 1))][log - 1]);
        }
    }
    vector<int> ans(Q);
    for(int i = 0; i < Q; ++i) {
        int s = S[i],e = E[i];
        if(pos[s] <= pos[e]) {
            int v = pos[s];
            for(int log = LOG - 1; log >= 0; --log) {
                if(log != 0) {
                    while(v + (1 << log) - 1 <= pos[e] && sp[v][log] >= L[i]) {
                        v = v + (1 << log) - 1;
                    }
                } else {
                    if(v + (1 << log) - 1 <= pos[e] && sp[v][log] >= L[i]) {
                        v = v + (1 << log) - 1;
                    }
                }
            }
            if(get_max(v,pos[e]) <= R[i]) {
                ans[i] = 1;
            }
        } else {
            int v = pos[e];
            for(int log = LOG - 1; log >= 0; --log) {
                if(log != 0) {
                    while(v + (1 << log) - 1 <= pos[s] && sg[v][log] <= R[i]) {
                        v = v + (1 << log) - 1;
                    }
                } else {
                    if(v + (1 << log) - 1 <= pos[s] && sg[v][log] <= R[i]) {
                        v = v + (1 << log) - 1;
                    }
                }
            }
            if(get_min(v,pos[s]) >= L[i]) {
                ans[i] = 1;
            }
        }
    }
    return ans;
}

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