oj.uz

Submission #1082305

# Submission time Handle Problem Language Result Execution time Memory
1082305 2024-08-31T06:24:18 Z jer033 Werewolf (IOI18_werewolf) C++17
0 / 100
 349 ms 50304 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 50304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -