제출 #393272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393272		79brue	늑대인간 (IOI18_werewolf)	C++14	0 / 100	313 ms	27992 KiB

werewolf

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

using namespace std;

typedef long long ll;

int n, m, q;
vector<int> ans;
vector<int> link[200002];
vector<int> order;
int idx[200002];

int MIN[800002], MAX[800002];
void init(int i, int l, int r){
    if(l==r){
        MIN[i] = MAX[i] = order[l];
        return;
    }
    int m = (l+r)>>1;
    init(i*2, l, m);
    init(i*2+1, m+1, r);
    MIN[i] = min(MIN[i*2], MIN[i*2+1]);
    MAX[i] = max(MAX[i*2], MAX[i*2+1]);
}

int rangeMin(int i, int l, int r, int s, int e){
    if(s<=l && r<=e) return MIN[i];
    if(r<s || e<l) return INT_MAX;
    int m = (l+r)>>1;
    return min(rangeMin(i*2, l, m, s, e), rangeMin(i*2+1, m+1, r, s, e));
}

int rangeMax(int i, int l, int r, int s, int e){
    if(s<=l && r<=e) return MAX[i];
    if(r<s || e<l) return INT_MIN;
    int m = (l+r)>>1;
    return max(rangeMax(i*2, l, m, s, e), rangeMax(i*2+1, m+1, r, s, e));
}

int bigLim(int i, int l, int r, int x, int lim, int dir){ /// dir 0: left, 1: right
    if(MIN[i] >= lim) return (dir == 0 ? l-1 : r+1);
    if(l==r) return l + (dir ? 1 : -1);
    int m = (l+r)>>1;
    if(dir == 0){
        if(x <= m) return bigLim(i*2, l, m, x, lim, dir);
        int tmp = bigLim(i*2+1, m+1, r, x, lim, dir);
        if(tmp != m) return tmp;
        return bigLim(i*2, l, m, x, lim, dir);
    }
    else{
        if(x > m) return bigLim(i*2+1, m+1, r, x, lim, dir);
        int tmp = bigLim(i*2, l, m, x, lim, dir);
        if(tmp != m+1) return tmp;
        return bigLim(i*2+1, m+1, r, x, lim, dir);
    }
}

int smallLim(int i, int l, int r, int x, int lim, int dir){ /// dir 0: left, 1: right
    if(MAX[i] <= lim) return (dir == 0 ? l-1 : r+1);
    if(l==r) return l + (dir ? 1 : -1);
    int m = (l+r)>>1;
    if(dir == 0){
        if(x <= m) return smallLim(i*2, l, m, x, lim, dir);
        int tmp = smallLim(i*2+1, m+1, r, x, lim, dir);
        if(tmp != m) return tmp;
        return smallLim(i*2, l, m, x, lim, dir);
    }
    else{
        if(x > m) return smallLim(i*2+1, m+1, r, x, lim, dir);
        int tmp = smallLim(i*2, l, m, x, lim, dir);
        if(tmp != m+1) return tmp;
        return smallLim(i*2+1, m+1, r, x, lim, dir);
    }
}

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)L.size();
    ans.resize(q);
    for(int i=0; i<m; i++){
        link[X[i]].push_back(Y[i]);
        link[Y[i]].push_back(X[i]);
    }

    for(int i=0; i<n; i++){
        if(link[i].size() == 1){
            order.push_back(i);
            break;
        }
    }
    while((int)order.size() < n){
        int tmp = order.back(), tmp2 = link[tmp][0];
        order.push_back(tmp2);
        link[tmp2].erase(find(link[tmp2].begin(), link[tmp2].end(), tmp));
    }
    for(int i=0; i<n; i++) idx[order[i]] = i;

    init(1, 0, n-1);
    q = 10;
    for(int i=0; i<q; i++){
        int s = idx[S[i]], e = idx[E[i]], l = L[i], r = R[i];
        if(s < e){
            ans[i] = bigLim(1, 0, n-1, s, l, 1) - 1 > smallLim(1, 0, n-1, e, r, 0);
        }
        else{
            ans[i] = bigLim(1, 0, n-1, s, l, 0) - 1 > smallLim(1, 0, n-1, e, r, 1);
        }
    }
    return ans;
}

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