제출 #1082319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082319		jer033	늑대인간 (IOI18_werewolf)	C++17	34 / 100	1172 ms	50420 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int NINF = -555'555'555;
const int INF  =  555'555'555;

class segTree{
public:
    int lef_index;
    int rig_index;
    int min_value;
    int max_value;
    segTree* lef_child;
    segTree* rig_child;

    segTree(vector<int> (&a), int l, int r)
    {
        lef_index = l;
        rig_index = r;
        if (l==r)
        {
            min_value = a[l];
            max_value = a[l];
            lef_child = nullptr;
            rig_child = nullptr;
        }
        else
        {
            int mid = (l+r)/2;
            lef_child = new segTree(a, l, mid);
            rig_child = new segTree(a, mid+1, r);
            min_value = min(lef_child->min_value, rig_child->min_value);
            max_value = max(lef_child->max_value, rig_child->max_value);
        }
    }

    int get_min(int l, int r)
    {
        int lef_overlap = max(l, lef_index);
        int rig_overlap = min(r, rig_index);
        if ((lef_overlap == lef_index) and (rig_overlap == rig_index))
            return min_value;
        if (lef_overlap > rig_overlap)
            return INF;
        return min(lef_child->get_min(l, r), rig_child->get_min(l, r));
    }

    int get_max(int l, int r)
    {
        int lef_overlap = max(l, lef_index);
        int rig_overlap = min(r, rig_index);
        if ((lef_overlap == lef_index) and (rig_overlap == rig_index))
            return max_value;
        if (lef_overlap > rig_overlap)
            return NINF;
        return max(lef_child->get_max(l, r), rig_child->get_max(l, r));
    }
};

int solve_query(int sloc, int eloc, int l, int r, segTree (&ST))
{
    if (sloc < eloc)
    {
        if (ST.get_min(sloc, eloc) >= l)
            return 1;
        else
        {
            int lo = sloc;
            int hi = eloc;
            while (lo!=hi)
            {
                int mid = (lo+hi+1)/2;
                if (ST.get_min(sloc, mid) >= l)
                    lo = mid;
                else
                    hi = mid-1;
            }
            //must be able to turn to wolf at lo
            if (ST.get_max(lo, eloc) <= r)
                return 1;
            return 0;
        }
    }
    else
    {
        if (ST.get_min(eloc, sloc) >= l)
            return 1;
        else
        {
            int lo = eloc;
            int hi = sloc;
            while (lo!=hi)
            {
                //finding the lowest value I can remain human in
                int mid = (lo+hi)/2;
                if (ST.get_min(mid, sloc) >= l)
                    hi = mid;
                else
                    lo = mid+1;
            }
            //must be able to turn to wolf at lo
            if (ST.get_max(eloc, lo) <= r)
                return 1;
            return 0;
        }
    }
}

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) {
    //preprocessing
    vector<vector<int>> edges(N);
    int M = X.size();
    for (int i=0; i<M; i++)
    {
        int x = X[i];
        int y = Y[i];
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    //create the line graph
    int leaf = -1;
    for (int i=0; i<N; i++)
        if (edges[i].size() == 1)
            leaf = i;
    vector<int> line;
    int prev = leaf;
    int curr = edges[leaf][0];
    line.push_back(leaf);
    line.push_back(curr);
    while (edges[curr].size() == 2)
    {
        int nex;
        for (int i: edges[curr])
            if (i!=prev)
                nex = i;
        line.push_back(nex);
        prev = curr;
        curr = nex;
    }

    vector<int> refs(N);
    for (int i=0; i<N; i++)
        refs[line[i]] = i;

    segTree ST = segTree(line, 0, N-1);

    int Q = S.size();
    std::vector<int> answers(Q);

    for (int i = 0; i < Q; i++) {
        int l = L[i];
        int r = R[i];
        int s = S[i];
        int e = E[i];
        int sloc = refs[s];
        int eloc = refs[e];
        answers[i] = solve_query(sloc, eloc, l, r, ST);
    }
    return answers;
}

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