Submission #1082305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082305		jer033	Werewolf (IOI18_werewolf)	C++17	0 / 100	349 ms	50304 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))
{
    //make sure there is no ordered pair of cities going from sloc to eloc such that the first needs to be wolf and the second needs to be human
    if (sloc == eloc)
        return 1;
    if (sloc < eloc)
    {
        int mid = (sloc+eloc)/2;
        if (ST.get_min(sloc, mid) >= l)
            return solve_query(mid+1, eloc, l, r, ST);
        if (ST.get_max(mid+1, eloc) > r)
            return 0;
        return solve_query(sloc, mid, l, r, ST);
    }
    else
    {
        int mid = (sloc+eloc)/2;
        if (ST.get_min(mid+1, sloc) >= l)
            return solve_query(mid, eloc, l, r, ST);
        if (ST.get_max(eloc, mid) > r)
            return 0;
        return solve_query(sloc, mid+1, l, r, ST);
    }
    return 0;//should never reach here
}

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: 0 / 34
• Subtask 4: 0 / 51